{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Travelling Salesman Problem\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "One of the most famous NP-hard problems in combinatorial optimization, the travelling salesman problem (TSP) considers the following question: \"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?\" \n",
    "\n",
    "This question can also be formulated in the language of graph theory. Given a weighted undirected complete graph $G = (V,E)$, where each vertex $i \\in V$ corresponds to city $i$ and the weight $w_{i,j}$ of each edge $(i,j,w_{i,j}) \\in E$ represents the distance between cities $i$ and $j$, the TSP is to find the shortest Hamiltonian cycle in $G$, where a Hamiltonian cycle is a closed loop on a graph in which every vertex is visited exactly once. Note that because $G$ is an undirected graph, weights are symmetric, i.e., $w_{i,j} = w_{j,i}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Encoding the TSP\n",
    "\n",
    "To transform the TSP into a problem applicable for parameterized quantum circuits, we need to encode the TSP into a Hamiltonian. We realize the encoding by first constructing an integer programming problem. Suppose there are $n=|V|$ vertices in graph $G$. Then for each vertex $i \\in V$, we define $n$ binary variables $x_{i,t}$, where $t \\in [0,n-1]$, such that\n",
    "\n",
    "$$\n",
    "x_{i, t}=\n",
    "\\begin{cases}\n",
    "1, & \\text {if in the resulting Hamiltonian cycle, vertex } i \\text { is visited at time } t\\\\\n",
    "0, & \\text{otherwise}\n",
    "\\end{cases}.\n",
    "\\tag{1}\n",
    "$$\n",
    "\n",
    "As there are $n$ vertices, we have $n^2$ variables in total, whose value we denote by a bit string $x=x_{1,1}x_{1,2}\\dots x_{n,n}$. Assume for now that the bit string $x$ represents a Hamiltonian cycle. Then for each edge $(i,j,w_{i,j}) \\in E$, we will have $x_{i,t} = x_{j,t+1}=1$, i.e., $x_{i,t}\\cdot x_{j,t+1}=1$, if and only if the Hamiltonian cycle visits vertex $i$ at time $t$ and vertex $j$ at time $t+1$; otherwise, $x_{i,t}\\cdot x_{j,t+1}$ will be $0$. Therefore the length of a Hamiltonian cycle is\n",
    "\n",
    "$$\n",
    "D(x) = \\sum_{i,j} w_{i,j} \\sum_{t} x_{i,t} x_{j,t+1}.\n",
    "\\tag{2}\n",
    "$$\n",
    "\n",
    "For $x$ to represent a valid Hamiltonian cycle, the following constraint needs to be met:\n",
    "\n",
    "$$\n",
    "\\sum_t x_{i,t} = 1 \\quad  \\forall i \\in [0,n-1] \\quad \\text{ and } \\quad \\sum_i x_{i,t} = 1 \\quad  \\forall t \\in [0,n-1],\n",
    "\\tag{3}\n",
    "$$\n",
    "\n",
    "where the first equation guarantees that each vertex is only visited once and the second guarantees that only one vertex is visited at each time $t$. Then the cost function under the constraint can be formulated below, with $A$ being the penalty parameter set to ensure that the constraint is satisfied:\n",
    "\n",
    "$$\n",
    "C(x) = D(x)+ A\\left( \\sum_{i} \\left(1-\\sum_t  x_{i,t}\\right)^2 +  \\sum_{t} \\left(1-\\sum_i  x_{i,t}\\right)^2  \\right).\n",
    "\\tag{4}\n",
    "$$\n",
    "\n",
    "Note that as we would like to minimize the length $D(x)$ while ensuring $x$ represents a valid Hamiltonian cycle, we had better set $A$ large, at least larger than the largest weight of edges.\n",
    "\n",
    "We now need to transform the cost function $C(x)$ into a Hamiltonian to realize the encoding of the TSP. Each variable $x_{i,j}$ has two possible values, $0$ and $1$, corresponding to quantum states $|0\\rangle$ and $|1\\rangle$. **Note that every variable corresponds to a qubit and so $n^2$ qubits are needed for solving the TSP.** Similar as in the Max-Cut problem, we consider the Pauli $Z$ operator as it has two eigenstates, $|0\\rangle$ and $|1\\rangle$. Their corresponding eigenvalues are 1 and -1, respectively.\n",
    "\n",
    "Now we would like to consider the mapping\n",
    "\n",
    "$$\n",
    "x_{i,t} \\mapsto \\frac{I-Z_{i,t}}{2}, \\tag{5}\n",
    "$$\n",
    "\n",
    "where $Z_{i,t} = I \\otimes I \\otimes \\ldots \\otimes Z \\otimes \\ldots \\otimes I$ with $Z$ operates on the qubit at position $(i,t)$. Under this mapping, if a qubit $(i,t)$ is in state $|1\\rangle$, then $x_{i,t} = \\frac{I-Z_{i,t}}{2} |1\\rangle = 1$, which means vertex $i$ is visited at time $t$. Also, for a qubit $(i,t)$ in state $|0\\rangle$, $x_{i,t} = \\frac{I-Z_{i,t}}{2} |1\\rangle = 0$.\n",
    "\n",
    "Thus using the above mapping, we can transform the cost function $C(x)$ into a Hamiltonian $H_C$ for the system of $n^2$ qubits and realize the quantumization of the TSP. Then the ground state of $H_C$ is the optimal solution to the TSP. In the following section, we will show how to use a parametrized quantum circuit to find the ground state, i.e., the eigenvector with the smallest eigenvalue.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Paddle Quantum Implementation\n",
    "\n",
    "To investigate the TSP using Paddle Quantum, there are some required packages to import, which are shown below. The ``networkx`` package is the tool to handle graphs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:24:17.197426Z",
     "start_time": "2021-05-17T08:24:12.896488Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import related modules from Paddle Quantum and PaddlePaddle\n",
    "import paddle\n",
    "from paddle_quantum.circuit import UAnsatz\n",
    "from paddle_quantum.QAOA.tsp import tsp_hamiltonian\n",
    "from paddle_quantum.QAOA.tsp import solve_tsp_brute_force\n",
    "\n",
    "# Import additional packages needed\n",
    "from numpy import pi as PI\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we generate a weighted complete graph $G$ with four vertices. For the convenience of computation, the vertices here are labeled starting from $0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:24:24.302458Z",
     "start_time": "2021-05-17T08:24:24.060967Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAAAz1klEQVR4nO2deXxU9dX/3ydkIewIiOBClEVFRXHXQq1a1/RR3LV2EVxqa/UpPLYabWsVNdalFLcuUHGrS6sVrWnr3p+i1bq2KiiIBGVVEAmQhYQ5vz/ODSRhEhJyZ+6dmfN+ve5rMtu9Z5LJ5557vmcRVcVxHMdJD3lRG+A4jpNLuOg6juOkERddx3GcNOKi6ziOk0ZcdB3HcdKIi67jOE4acdF1HMdJIy66juM4acRF13EcJ4246DqO46QRF13HcZw04qLrOI6TRlx0Hcdx0kh+1AY4uUdJWUUeMBQYARQDhcB6oAaYC8yvLC9NRGeh46QO8daOTqoJRPZIoBQYC+wOJIAGQIJNgy0fuwKbA7wEVADPuQg72YKLrpMySsoq+gLjgUuBnkB3TGDbiwLrgCrgFmBGZXnpqrDtdJx04qLrhE5JWUU34JfAeZhH2y2E3VZjHvB04LLK8tLqEPbpOGnHRdcJlZKyirHAQ0BfLF4bNjXAKuCMyvLSWSnYv+OkFBddJxRKyiqKgCnAOaRGbFtSA9wNTKwsL61Lw/EcJxRcdJ1OU1JW0QN4GtiH9AhuIzXA28AxleWla9N4XMfZalx0nU4RCO4sYFegawQm1AIfAmNceJ1MwIsjnK0mCCk8TXSCS3DcXYGnAnscJ9a46DqdYQoWUohKcBvpCowGfhWxHY6zRTy84GwVQZbCU6Q3hrslaoCjPash88ilKkUXXafDBHm484DBUduShCXAcM/jjTe5XKXovRecreFGLA83jvQFbgAuidoQZ3M6WaW4LxZGOheoKimryMgqRfd0nQ4R/NMsIfo4blvUAoMz7Z8xm/EqxU34QprTUcZj/zRxJoEVaTgxIIj/z8M81K6EI7gE++ka7HdeSVnFmJD2m1Lc03XaTRCHWwQMitqWdrAE2DFT437ZgFcpJsc9XacjHInF4TKBXsARURuRqwRFMy+QPsElOM45wPPB8WOJi67TEUqxhY9MoBtwfNRG5CJNqhRHk/6UwmJswW1WXIXXRdfpCGPpWD/cKMkDvhq1EbmGVyluGU8Zc9pFEM8dGeY+bzltb74ytD99uxewrm4D7y7+khv/8SHvL60K6xAjS8oqpLK8NC4LF/nAT7AqPsXizsuBlcAXwW3Tn2sjsbJzxLFK8aKIbWmGi67TXoYCG8Lc4fZ9inltwUrW1DZwyNB+HDZiW4YO6MGYG18I6xAJzO6PwtphJ+gJPAnsT/PV+was8qoBE2IBCoAi7Pe9BlgNfA68DPwa+CRdRneEIEvhHOJTpVgMjC8pq3gwTlWKLrpOexmBCUNonDnt1Y0/7zG4FxUXj2VQ72Ly84SGRCjOaQNmdxxE91LgIExMm5JP6/+HecA2wbYzsB9wCuZJxioHOcjDfYj4CG4jxcDDJWUVsalSdNF12ksxKYjnfueQIQzftieHDu0HwLSXPg5LcMHsjYsIHMnmgttRugADgRnAuM4aFDJepdhOfCHNaS+FpEB0j99zEN8+eAhDB/RgyZc1vLkwVAdO6LzQhUVYuc1FwF4h7SsUgirFc4nPCa4lxcD5gZ2R46LrtJf1WMwxVM6c9iq7/uzvnH/vGwzs1ZU7z96X7fuE87+bqKvu+fkTN00VkbdE5BkReVhE7hSRySLyIxH5joiUisjBIjJcRPqJSJdQDr45vZveWblyJYcddhhDhgzht7/97cbHKysrmTJlCtOmTWP+/Pmt7SsuC4ONeJViB/DwgtNeagjxn70oP4/6DQkSCnUNCf7f3M9Zt76BXl0L2Gmbbiz+sqbzB1ElUbuuP9C/I+8SkVW0nlHQ2v112nZ5Z7OikoKCAsrLy5uJ64IFC5g2bRoLFiygrq6OefPmMXnyZIqKNnPWV3bg86SUIKvlUsIr7U0V3YBLS8oqpkZdpeii67SXuYT4fRm9Yx+mnjmafy/4gtU19RxQsg29uhawYm0d7y1eHcoxpKhbdXHJ3t+o/fiNNUC/Jts2bdzvzabFq46wXkSSinSvXr1Wr1q1qiAvb9OFZa9evTj00EN56KGH6NfP4tmPPPIIq1at4sEHH0RVOf/883n88cc5/fTTUVVENkZ3Pt+KX0eqyMQqxWejNMJF12kv8wkxHLV8TR0LVqxjzPD+dC/M54t163nyv0u49fl5rKkLJ0lCRKTXgSf984vnprfbQxeRfGzhpT0C3fR+MbBdsDWjW7du1NbW0q3b5s7gihUr2GsvC9G++eabHHDAAY12UFdXx9KlSzd7TyKR+KypgEdMJlYpuug68aeyvDRRUlYxByux7DQLVqxrljKWImZ3tDBCVRswT7JD3qSIFLO5KG8D9Bs1atQI4Gws/7YZVVVV9O9v0Y+lS5cycODAjc8tX76c3r2bhYJJJBJcf/3143/2s5+dyJbDHh0NgWwNoVYpFuXnUXbc7nxj1CB6FOXz3uLVXPu3Obzz6Zdh7D4WVYouuk5HeAmr8smEUuAE8GK6DqaqNVgHtkVJnj4MOIkWi2kNDQ2sWbOGvn1tUb2uro4BAwZsfL6qqopBgyzpoTG0UF9fz+effw4hh0CS3N/4s6quT7azVFQp/vwbIzn7oCF8sKyKV+av4Bt7Dea+CQfy1ZteYFV1fRiHiLxK0UXX6QgVWGpQLBuJtKAa+FvURgRsQ5ITVX5+PqrK3nvvDcCee+7JwoULAfNyi4qKGDJkSLP3FBUVrb3xxhsvuvXWW/9O62GPDodA2kJE1pJEoIt23FMHnnltnnQJR0b6dS/ktP12ZENCOXv6a6xct56GhHLy6B347iEl/Pq5eWEcJvIqRRddpyM8h5WlZoLoVgHPR21EQD+ssGEjV1xxBQ8++CALFy5k7NixXHnllfzgBz/gmmuuYeXKlcyePZuTTz6ZkpKSlvvaUFRUtEJVwwqBtEewewTbTk33l1fYFa2vRbqE83UYMbAnhfl5fPpFNSvXmXP97qLVnDx6B0YO6hXKMYhBlaKLrtNugrjuzcBk4p0iVA3cHHVqUBP60CKeO3nyZCZOnMjq1atZtmwZAwcOZPjw4Xzzm9/k1VdfZZddduH73/8+hYWFyfa3VSljWwiBJEUsrtGLJKJcuN2wsXQpOBErnOk0/XvYbtat37SQWr3e2n0M6BlajUvkVYouuk5HmQFcF7URWyAPmyAQF9bRollQly5dGDBgAAMGDGDYsGEbHz/99NM5/fTT29pXF9KYpxssvK0Oto+bPldSVrESOJaQRHfFWvNuuxdukqXuRXaB8Pma0AZBRF6lGJu8EyczCIY9TseKJeJIDTAtZkMpnwTCUo0iOuCppphQqxTnfbaG9Q0JBvcp3uj1jtqhDwBzloXW7lMJ72+xVbjoOlvDZcSsy1UTvgAuj9qIFnwKHIOFPVZjcfFaOi5Y1ViOaVz67IZapbhi7XoeeWsRXfKEP557MLedOZoTRg1mbV0D9/xrYViHUSJ2GDy84HSYyvLS6pKyijOwCQFxanJSA5wRlxZ+Lfg31iFsP2BHNsVGB2PZBAPYVBHXC4sB12ELPwnsEv4J4LvpNrwNQq1SBLj6r+/TsCFB6V6DKOk3kLc//ZLr/jabL9YlzVrbGvIxuyPDpwE7W01JWcWdxKdpdQ0wo7K8NFZTAjpBAZuEuQd2ZfERMWp2E+TpriUef//2UgN0jzJP18MLTmeYCLxN9Je7tYEdkyK2I0zqsVE+szEveR4xElywbBZgTtR2dJAOVymGjYuus9VUlpfWYbHKDzWRCO36r4PUAh8CxwT2OOnlJWJ2MmiDtFYptoaLrtMpKstL1y6779Lz1i+b1yVRn3bNqwHeAsZUlpeuTffBHcCqFNdFbUQ7iUWVoouu0ylEpF/d4g8eXvbHy7rUfPzmR0ECfjqowXKGj3DBjZTGKsVMIBZVir6Q5mw1IlIA/APrUfoWMHbI5U/uCzyMtUdMxQJLDbaodEacJrzmKiIyrO+R5z/QY+9jDsgrjHrqeptUAz+tLC+dErUh7uk6neEWTHCXA+NUtToQwuFYAUUt9mUPg+pgf9OB4S640SIiw0TkbuCD1bMeOACJfeO52FQpuqfrbBUicj7we6wq6Wuq+q+WrwkGAZ6DjXPphfVraPeJXhMJtGG9SkHRUhG5Gbg7ZpVmOYeIDAN+CnwLK0neANy9w8X3FXbp3vdU4pk+VgNMrywvjcU0YBddp8OIyFgsllcATFDVGW29PsjnPBI4DmsiPRJbSW7AauEFWwFXLHk9T1Vnr3mrYveauf/qVrfkg70T62v/m7IP5GyRVsT2HuA6Vf24pKyiG5bWNjg6K1tlMTAiLkUzLrpOhxCRIcAb2LDHKara4dzYQIR3wVrsFWP9BOowj2QuML+yvFRFZDrWv/fnqjo5pI/gdIBAbK8Evk0SsW362pKyijHEs0rxqMry0pejNqQRF12n3YhID+BlYBT2z1UajLdJ1fG+AfwVeFtVQxkT5LSPjohtU7xKccv4QprTLkSkcSFiFHYZeWYqBTfgWSwHdHTgYTspJlggmwF8gIknwF3ACFU9ty3BDfAqxS3gouu0l58Bp2C5jieoasoXtFS1Fvh7cPfEVB8vlwlBbIHmVYpEJ7yxrlJ00XW2iIicAvwCW+g6U1U/SOPhZwa3J6XxmDlDWGLblKBYZQzmaaa7jWLsqxQ9puu0iYjsDbyCpXv9WFVvTvPx+2CzwPKAbVU1bVMTshkRGYplIzSN2d6LxWznh3GMkrKKIuBXwHjSE+NtrFKcFEcPtxEXXadVRGRb4HVsIOF9wHc1gi+MiDwNHAWco6r3pPv42UQgtlcC3yFFYtuS/sf/7/iuu+x3V17X7uQVpKRqLaOqFD284CRFRAqBRzDB/TdwQRSCGzAzuPUQw1YiIkNF5C4s1jk+eHgGsKuqTkiV4IqIrPz7reOX/O4Caj95t3GBLaerFN3TdTYjmAD7O+B8YAlwgKouidCe7bG5YDVAf1WNRZJ7JhCFZ9vi+GcAD2EhohFDLn9S6ESVIlZUU40t6GZklaKLrrMZInIRcDvmRXxVVV+P2CRE5DXgQOAkVZ0ZsTmxJ2qxDWzohi3Q7YhdKU1rfG5rqhSxhu4vYu0Znw+aqGccLrpOM0TkCKzwoQtwtqo+ELFJAIhIGXA9cK+qxmlOWKxoRWzvw8T2ozTbchWW9fIOsL+qbmjtte2tUkyxyWnBRdfZSPAP+29sNtcNqloWsUkbEZHdsNEwq7AshlQXZmQUIrILJrbfJWKxDezZCfNyi4HDVDXyiQ1xwRfSHABEpBc2bXYb4EksnSg2BLnBH2J9esdGbE5sEJFdROQPmDc4IXj4bmA3VR0fheAG/BIT3D+54DbHRddBRLoA92NxtTlYWKHVS8EImRnc5nwWQ4zFtrEL3ZnYmsBPorIjrrjoOgCTgf/BLt1PUNWqiO1pjceC23FBhkXOEWexhY0n8KnB3V+q6sIo7YkjHtPNcUTkLOABLAZ4jKo+F7FJrRI03VkEDAL2U9W3IjYpbcQtZtsaInIulje7CMsB9vS+Frinm8OIyP5YnT3AxDgLLoCqJoDHg7s5EWJoxbO9h5h4tk0Rkd5YhglYybgLbhJcdHMUERmExUi7Yp7J7ZEa1H42hhiiNCLVBGI7HVs8nIDlrTaK7TlxEtsm/AzYFuu5/HDEtsQWDy/kICLSFfgncBAwCzhSVddHalQ7CcqTP8eqmYbHVHy2GhHZmU1hhHysYKAxjDAvStvaQkR2Bd7DQh8HqOqbEZsUW9zTzTGCBajfYoL7KXBKpgguQGBrRXB3XISmhIqI7Bx4tnOxEUV5NPdsYyu4AbdgJ4m7XHDbxkU395iIeVHVWKbCZxHbszVkTYghC8QWETkOKAXWYF660wYeXsghRORYzEvMA05X1T9HbNJWISI9gRXYNOJBqro8YpM6TCthhPuBazNBaBsRkQLgXWBXIui3nIm4p5sjBDG3h7C/+TWZKrgAqroGm58mwAkRm9MhAs92Gs0923sxz/a7mSS4ARdhgjsPuDViWzICF90cIJi+8ATQG/gLcHWkBoVDRoUYWojteWS+2CIiA7CGNmAphxmzNhAlHl7IcoIKoQpsWOB/ga+oaixnR3UEERkILAXqsR67ayI2KSlBGOEKrIdsxoYRkiEivwMuAP4BHB9hk/uMwj3d7OeXmOCuAE7MBsEFCOK4rwCFWE/WWJGNnm1TRGQfrMl9AzDJBbf9uOhmMSLyXeD/sH+MU1S1MlqLQid2IYZsF1vYmHY4FYup366qcyI2KaPw8EKWIiKHYAUQhcD3VPX30VoUPiIyDFvAqQIGRBlTFJESLBvhHDaFEf6IhRHmRmVXKhCR04A/YVdPI1Q1o8blRI17ulmIiOyAeYGFwB3ZKLgAQTXae1h12uFR2CAiJSLye0z8Gz3b+4DdVfU7WSi4xdhsMoCfuuB2HBfdLCOYSzUTGAi8gBVDZDORhBhaiO35ZLnYNuFSbEL0f7CeHU4H8fBCFhHE2h7AGkgvwGrgV0ZrVWoRkX2BN7FMhh2CTmSpPF4Jlo0wniwPI7RERHbEGvAUA19T1f8XsUkZiXu62cXlmOCuxUp8s1pwA94GPsF67B6YqoPksGfblBswwf2zC+7W46KbOTSOpU7+pMgJwHXYyOqzVfW9dBkWJUGq0szg7riw99+K2N4PjMwhsUVEvgJ8Ex/B02lcdONNPtYRbCVWBDAPOLjli0RkD+wSV7DFjSfSaWQMmBncjgtrhyIyJEj+Tya231bVD8M6VtwJJnY0juC5KQtTD9OKx3Tji2C9Er4BdGvyeA0wCRNjRKQfNjZ9F6xx9Fm5lqguIvnAZ9ik4JGdyRsVkSFYzHYCm2K2D2Ax25wR2qaIyATgD8BibATPuohNymjc040vP8Ha5XVr8Xgx1rt02tVXX10M/BkT3LeACbkmuACq2gD8Nbg7bmv20cSz/Qgrbc1Zz7YpItILKA/u/sQFt/O4pxtPjgcewQS2Narnz5+/5sADDxz4xRdfLMcyFT5Nj3nxQ0TGYelj/1bVgzrwvkbPdjzWKjLnPdumiMiNwI+xkusxuXhSDxsX3fixG/A60GNLL6yrq2PVqlXcfvvt37r22mv/mHrTYkM37MTUDfNwVwX5ySuwE9UOqrq4rR20IrYPYmL7QQptzxhEZDjwPhZmOVBV34jYpKzARTde9MUaQg+iSehn9erV9O7dO+kbEomE5uXlVWMry9m+gNYL+F8s9KJY3LsAW+S5TERmAicCF6nqncl2EIhtGRazdbFtAxF5AvgfbATPuVHbky246MaLvwFHAEWND0ycOJGPP/6YPn36MHHiRPbZZ5/W3luD5VFOxgQpm2gqtnlsHueuBo4PChfuBp5R1aObvsDFtmOIyDFYy8Y1WH+FZRGblDX4Qlp82Bc4jCaCO3nyZD744AOmT59O//79ueKKK2hoaGjt/cWYKP2ONvJ5M4xu2FjvxVjhRw82F9zG103t0aPHk5iYHh40bm9cIPstlvr1PWxa7R+BPVT1Wy64mxOM4JkS3J3sghsuLrrxIQ9rwQjAggULePbZZ7n11lsZMGAAt9xyC/n5+bz99ttt7aM7FmY4MsW2poOhWMlpW2LblGFr1qwZDbyIxSC/42K71fwA2B3L5PARPCHjohsfFtPEyy0pKWHq1KnstNNO1NfXA9C7d29eeeUVAD777DOWLl2abD+CCVam82Mstp1UbDds2NDyoe7AzSLyz+D+rzGxzcfFtt0EI3gaxzlNUtW6KO3JRlx048NSYAawDkBEGDVqFEVFRRQUFABw8MEHs369tYw9+eSTmTMnaQ1APtAnHQanEAHOwLzTZjz22GOccsopXH/99Sxb1vyqt7a2do8jjzzyp0328RCWZ+ti236uwWbpPQ08GbEtWYkvpMWLPGwx7CKSeHizZs3i3nvvpaqqioEDBzJ16tTNdoCJ9nBMxDMVwUqf+zY+sHbtWk466SRUlUmTJjFjxgx22mknbrrpJvLyNvkO77zzDvvuu+8qVe0L/I+qunC0ExHZGyuyUWCUqs6O2KTsRFV9i992pqqu0yYkEgl99913VUT01FNP1VZYp6qnx8D+MLYpqlrb9MO99tprG3/+61//qpdccslmv4ANGzZU//CHP5yBCcf0GHyOjNiwE90Lwe9tatT2ZPMWuQG+Jd+WL19+0KpVq+rr6uq0KTfccIOuW9dMjxtZq6o3RG13iNt2qlqd7IPedNNNWlxcrOPGjdM//vGPWlvbTJt13bp1HwTi8RnQJcm+82Lw+WK1AacEv7MVQN+o7cnmzWO6MUREZODAgefttttu+R999FFDIpGoaXzuJz/5Cd26bRZ5qAVexiqssoVlWJOVzRZyhg8fzttvv80vfvELXn75Ze6///5mzxcXF+9QWlq6FBgAHIqFbQ7B0qAqgfXAv4B2lwtnMz6CJ73kR22Ak5SLgPOWL19ee9xxxx25cOHCi7HKoO42HKIZG4AlwKlYjmo2cV0ikTivacwW4MQTT9z4c79+/ViwYEGz50Wk+x133LG2oaGBsrKy3wLbY8JbzKbv/EHA81g5ca435J4ElAD/BaZFa0r2455uzBCRI7F0J4BzFy5c+AqWe/sLrOqsKYotnB2FVQ5lDSKyo4j8/De/+U1hbW1tq69bvnw522+//WaP77TTTgP/9Kc/MWbMmJHYanxPmjsZgonw5HAtzyxEZHs2XSH9SFU3y8VzwsVFN0aIyFCsVWMXoFxVHwieUuzy70Qs5rYGE9tVWBXbx+m3NjUEYnsnMB/4/uTJk0VENgqBqrJs2TKuvPJKRo8eTX19PWeddVay/dCrVy+6dNks66zZyzCPt0+4nyKj+CWWKfOoqr4QtTG5gKeMxYSgb+m/gJFY56xxmnzIYndgL2A5FlbIiuT1YOhhGTbGvAA70TyElaF+H+txWwRQVVXFPffcw/HHH8/QoZ2uA1kDXIi1c8w2TgXOwqaN/AMb57TxBC0ih2JrAXXYrLcFyXbihIuLbgwQkS7YyJlvALOBQ1S1KlKj0sQWxLax+mMgNt24rf7CHUZVCWLkf8diu9nEBOA2NuV7N2Ajn+4ArhGRdcBrwP7Adar606R7cULHwwvx4FpMcFdhU3yzXnBbhhGweOuDWLnuN7X5yJ3lwHQ66dWrKjU1Naxdu5Y5c+bQZFHycKBrZ/YdM7ajueCC/X6Lsb4KC6dNm/ZbEdkfu1q6If0m5i7u6UaMiHwT6w2wAThGVZ+L2KSU0opn+zDm2bZVAbUt1oClZ4vHG2hHFs68efP4zW9+w7Jly3j99dfZbbfdOPDAAzn99NPZddddq7DFyoqt+Ehx5AEs77awtResW7dOFyxYINOmTbtq6tSp16TPNCfyROFc3oADsIwEBX4YtT0p/qw7Ype2dcHnbexnO7ID+zlJVdeo6mpVrVIrnnhArTCkVa6++modNmyY7rfffnr88cfr448/rqqqkyZN0osuukhVNaGq90T9OwppO0BbKSppyYYNGzSRSFSr6p9VdXAMbM+JLXIDcnXDOmgtDgTo9wRXHdm2hSS2TbcCVT1KrVS6l1p12SpthXfffVfPPfdcbWhoUFXVN954Q0844QRVVV24cKHusssujS/9MOrfVQibqOp/1E4iHaFOrYT8SlVNVsHnW4ibx3QjQES6YkMUBwOzMC83q+I8Qcz2Diwk8AMslPAQsKeqnqVb30ylHngm2FcVJuKP0kphSEFBAW+88QZdunShrq6O5cuXo2qx3Z122omrrrqKtWvXJrBKtUznLKyt58Zg9YIFC3j++edZsGBBWw3wC7H47xVY/wXXhRTiMd00I7Z6cw/wbeATbIrvZ9FaFR5BzPZyLGZbSPtjtp3hKGx6cq9kTx577LHsvvvujB49mqeffpqzzz6b4447jvXr1yMiFBQU1GD5uu+myL50UIgtivVrfGDZsmWcdtpp5Ofn061bN8466yy+9a1vbWk/a7Hc77dSZ2pu42e09DMJE9xq4MRsEVwR2SGJZ/swsFcnPdv28P9oYzHttttuY//99+fFF19kzJgxjB07FmBDYWHhmoKCgs8DezNZcMGyX5otnF1xxRUce+yxvPDCC1x88cVMnjy5tR7MTSnATmJOqog6vpFLG3AclqWgwClR2xPSZ9oBuJ3mMduHsNSvdNryiKpu0DaoqanR+vr6WlVdqtY68lDNnhjmqWoLjKqqumjRIj388MN14cKFGz//xRdfrNdee62qqn7yySf67LPPJvs1rVHV82LwebJ2c083TYjIbpgY5QFXq+qjEZvUKQLP9nYsz/Yimnu2Z6rq+2k2qRzrttaSaqB2xYoVK6677jqOOOKIf2Cx9InAK9hJMBt4gSa5xttvvz233XYb22yzzcYXjB8/nvfftz/LJZdcwkcffZRsP40nTSdFeEw3DYhIX+BVYAS26HO6Ji/xjT0isgMWsz2fTTHbP2Ex23QLbUuOxwYpDsZOAu9g8fPHRaQ7MAcrQBmoqvVRGZlCbsJCJd2gWcUd9fX11NTUcMEFFzBs2DBee+01nnnmmZbvX4eFv36fRptzj6hd7WzfsFjjPzBxegfoHrVNW/k54hJG2NKWp6rDVbUoyWeYE9h+RAzsTNVWqqpLtJXc5UmTJqmI6PPPP5/s6bmaPeGW2G7eTzf1/BI4BvgcWzhbF7E9HaIVz7YxGyFqzzYZCWzsejJmYp9lHNZLNxupAHYGJqrqz+rr64sLCws3ppBdcMEFFBcXc/jhh7d8XzWWcZIt4ZbY4uGFFCIi52ATfhsw7+qlaC1qP62I7Z8xsX0vStu2FhE5CAvzfAoM0Sz/8h922GHjL7zwwrvGjRtH165dNUhXJJFI0KIxfD3wFNYo30kxLropQkQOAf6JCdYFqpoRHfmDptaXY60Us0JsGxGRPExwBwP7q+qbEZuUMoICnNnAzhMmTLjxD3/4w7FY4UT3JC+vAXYHFqbRxJzFsxdSQFAg8BgmWrdnguCKyPYichvWb/WH2ELUn7BR3GdkuuACqC1ePh7cHRehKelgEhZmeO+uu+66EtgHO5F+gYUSwEIx67BMDhfcNOGebsiISDfgJWBfLG54rMZ4pTybPdtkiMjR2KX0+6q6Z9T2pILgb/oh5tV+XZt3ruuOhYzOxkItTwDPYn93Jw246IZIEDN7EDgD8xgPVNWV0VqVnCRiC5tSv7JObBsRkUJsNHtvYISqtrbolrGIyL1Y1eNjqnpy1PY4zfHwQriUYYK7FmtGHjvBTRJGKMQ8272yJYzQFqq6nk19c09s67WZiIgcjAluHXBpxOY4SXDRDQkRORGbQaXAN+OWThWI7a1YBVlLsT0928W2BTOD25OiNCJsgoXCqcHdW1Q1awaWZhMeXggBEdkTGyrZA7hCVcsjNmkjQRjhMpoMdsTE9pocE9qNiEhPLG+6EBisqssiNikUROQ7WAXeUix0sjZik5wkuKfbSUSkH7YY0QOr0IrFvKkWnu3FmOD+GctGyDXPthmqugZbPBKyJDc1OJE0fvcuc8GNLy66nUBECjAh2xl4Ezg36oT7dohtprcwDIuZwW22hBjKsGkkr2Ez95yY4uGFThB02boIm1a7v6ouitCWwWzKRmgaRpjsQrs5IrItsAyrxhqgGTyBWUSGYoUQhcDBqvpaxCY5beCe7lYiIt/DBHc9MC4qwRWRwSIyFctGaPRsH8E92zZRax7/MiZUx0ZsTme5Gfsc97rgxh8X3a1ARL6KddwCK/F9NQIbmortJTQX29NcbNvFzOA2Y0MMIvJ1rLpuHRZicGKOhxc6iIiUAK8D/bG0nLTmQgZhhMuA77EpjPAIlo3gQtsBgsvyj4A1WIihLmKTOoSI5GPtQvcgZlkzTuu4p9sBRKQHVrvfH+uRe1kaj+2ebcio6nxsNlpP4GvRWrNVfA8T3I+BKRHb4rQTF912EiSe3wuMAuYCZ6lqynuPutimnJnBbUaFGIJUxcnB3f9T1WSjipwY4qLbfq7C/jFXYyW+X6byYK2I7aPA3i62ofJYcHticGLNFH4B9AWeY1PnNCcD8JhuOxCR07BmMAngeFV9KoXHGsSmmG3joMFHsZjtf1N13FwlaFJUCewEHBLFomhHCSog38GKO/bO5UKXTCSTzuyRICKjsdJKgB+nSnBFZJCI/BrzbP8XE9xGz/ZUF9zUEBSzzAzuxj7EEJwkfg10AX7jgpt5ZJWnW1JWkYd1xx8BFGO5i+uxzvhzgfmV5aXtnsIrIgOxTIUdMeEdH3bFmXu20SMiX8NGmM8Ddo26qrAtRGQcFhJZBQyPYyc7p20yWnQDkT0SKAXGYiNHEthMMgk2DbZ8zLOfgzUZrwCea02Eg76rzwNfwZo9Hx7mYoWLbXwIUq+WA9sAI1V1TsQmJSUYwfM+sAtwsarevoW3ODEkI0W3pKyiLzAe6xfaE+uGL22+qTmKJZNXAbcAMyrLS1c1Phlcwk0DzgUWAweo6tIwbG9FbP+Cie1/wjiG03FE5G7gu8CVqnp9xOYkRUQuB8ox4d1HVRsiNsnZCjJKdEvKKrphI83PwzzabiHsthrzgKcDl1WWl1aLyMXArUAtMFZV3+jsQQKx/QlwIS62sSPohzwTeF1VD4zYnM0IimLmknwEj5NB5EdtQHspKasYi7VO7Msm0QqDRuE+Fzi57+Hjb8Jq2QEmdFZwXWwzhmew2P8BIrJDlM2LWuF6THBnuuBmNrH3dEvKKoqwaptzsMWxlJKor2Ptu8/y5T/vvjFRV73VFWcutpmHiDyG9TH4oareEbE5GxGRA7GWjeuxmPP8iE1yOkGsRbekrKIH8DQ2PjrlgtuINtRvoEv+ayJyTGV5aYeaQbvYZi5NJi88q6pHRW0PbKyEfAU4CLhBVb2pTYYTW9ENBHcWsCvhhhPaSy02xnpMe4TXxTbzCUprl2MLrduq6qotvCXliMi3gPuw3r8jgqkXTgYTy+KIIKTwNNEJLsFxdwWeCuxJSlDUMAUravhR8L7HgNGqeooLbuYQ5Ly+iK11lEZsTmODpV8Gdy93wc0OYim6WAx3H6IT3Ea6AqOBX7V8QkS2E5FfkVxsT1bVd9JopxMejb0YxkVpREAZMBgr0LkvYluckIhdeCHIUniKNMZw20ENcHRleeksEdkOCyN8n00nhcewMMI7EdnnhISI7AQsxPK4B6hqTUR27IKN4CkiQ3pCOO0jVp5ukIf7EPESXIBiTSQe6VLc81ZgATAR92yzElX9BHiLIB82QlNuwgT3Phfc7CJWogvciOXhxg7dsH5g7zFnX4yLbS4QaYhBRI4ATsZH8GQlsRHdoLT3XOLn5QKQV9CVnqOPTXQt2ecwF9usZ2Zwe4KIdEnngYM+EL8O7l6vqovTeXwn9cRGdLFeCu3uABYF0qWgduCZ1+4XtR1OynkfmI+NZfpKmo99PrAX1uN3swVcJ/OJhegG3cIuJZxeCqmkG3BpYK+TpQStHdMeYhCRbfARPFlPXMTjSKxbWCbQCzgiaiOclDMzuB0XdJ1LB78A+mG9fR9r+6VOphIX0S3FVoszgW7A8VEb4aScV4HPgJ2xYaQpRUT2AH6Ahdh+FOdG6k7niEuXsbF0rB9uq0z4Sgmn7bcjIwb2pEue8Otn5/Lr5+aFsetG8oCvhrlDJ36o6gYReQJrIzoOSFllYeBJT2HTCB5vYp/FRO7pBvHRkWHtb8/te7O6pp6lq1Oa0z6ypKwiXZecTnSkK677P8BR2Aien6X4WE7ERC662EyzDWHtbNKf/sOZ015l9pKqsHaZjARmt5PdPA+sBfYRkZJUHEBEitiUpXCVzzzLfuIguiOwmWaZRANmt5PFBNkDfw/ujkvRYf4XO4HPBn6bomM4MSIOoltMSPHcNCLEtIjDCZ2UhRiCPh6N4YQfqWp92Mdw4kccRLeQzBTdVts9OlnF34B6YKyI9A9539cDPYAnVPWZkPftxJQ4iO56rGl0JqFAXdRGOKlHVVdjebN52IJXKIjIAVgVZj3wf2Ht14k/cRDdGkIU3TP235GbTx3FHtv3BuDokQO5+dRRHD1yYFiHINGwvnDNW38bKSI7pjFx3omOUEMMwXdmanB3iqp+FMZ+ncwgDnm6cwnRjgNK+nLqfjtuvD9ycG9GDu7NolU1PD17eTgHSSS6Vv37sWuAa4A1IjIbq9dvui3OkAR3wSZkbAA+wT34ZDwB/AY4WkS6q+q6INVxKLagWoyFydZjTsRcYH5leWlrvUS+CRyCjQa6LtXGO/Ei8ibmwZd3LRm0MKUbGjZ8ctO4WcAeWFOUZFRhK9ItxXhJjMR4APAgJgAJ7G/wGWbnv4F3sc8wm8zLMAkVyct7teuQvQ/q87VznizabthgYHfsd9aAnbgEu2JTzInIA+YALwEVwHOV5aWJYATPh9hEiPGqenfaP4wTKZGLLkBJWcWbwL5R29EB3qwsL90fQES2xYo79mix9WvlvasxUWspyEvTLMZ5mGc7APPSWpLAToYSvHYqcGXarIsJQcvR8Ym66l8APaWwq4rkdSSkpFhf3CrglkV3jh+0oerzS4E3gINUNdad9ZzwiUN4AcwbGE1mZDEksOGFAKjqZ5h3+M/Gx4KY3baY+LYU5G2AQ4OtKV+KSKMANxXkZSkS4wOw5j3JBBdMaHs1uf8jTChyohFLMMXkl1gZcCKvqFtjB7yOfkcFy1DooZq4dvAFvyte+5+nWPPmkz+uX7nIBTcHiYunexQ2rrxH1La0g7XASZXlpc929I2BGA9kkwA3FeTWJmasYpMANxXj5Z0U44uwkTDNwjqqShtrgytpPZySNQRz+h7C/iahh70SDfUb8vILlgNnVJaXzgp7/068iYvo5gGLgEFR29IOlgA7trFI0mECMd6O5GLcp5W3fUHz8ESjIH/WTjH+AzCh6QONgvvOO+8wb948hg4dyqhRo8jP33hBtJbMacHZYUrKKoqwxjPnkJ41hhrgbmBiZXmpL2DmCLEQXYCSsopJWAPnODcyrwZ+WlleOiUdBwvEeBDNwxONgty7lbetZPPFu9lBGKQp7wB7t3zzX/7yF55++mk+//xzPvzwQy688EIuvPDCRuH9mCztOVFSVtEDeBrYh/Qu6tYAbwPHVJaXrk3jcZ2IiJPo9sW8yK5bem2E1AKDK8tLV0VpRCDGg9l88W4kzeOwTVlBIMJ5eXnv19XV3ZKfn7/Z73qvvfbigQceYK+99gKgqqqKnj17NoYcHieiYY2pJBDcWVjqXBTfv1oso2GMC2/2E4fiCAACIZuOnfnjSA0wLWrBBRsno6qLVfVpVZ2iquep6iFYKGJH4Fisyuku4DVgDRaLPQz4Qf/+/e9oaGjYTFxef/11ioqKWLBgAY8++iifffYZvXr1ahTceiyNLKsIQgpPE53gEhx3V+CpwB4ni4mN6AZchi0cxZEvgMujNqItAjFepKpPqeqvVPVcVT0YC0XsBBwHXPr1r3/97/X19Zu103zjjTdYvnw5c+fO5f777+e66zbl7Tc0NKyfP3/+wrR9mPQxBQspRH2F1RXL4PFhlFlObMILjZSUVYzBPI84FUvUAEdVlpe+HLUhIfFDLHOhmdBcddVVvPvuu/zlL3/hyy+/5JJLLmHcuHGcfPLJrF27ln322Yf58+cvI0mesarG9WTZKkGWwlPE77t2tGc1ZC9x83QJvmx3E58wQw0wI4sEF2A/knh2VVVVHHLIIRvv9+nTh1WrTEuLioq0srKyGsuyOBK4GOv/+hLwhYgsEZFnRGSqiFwgIl8RkT6p/yhbR5CH+xDxElwwex4O7HOykLgUR7RkIrayvi/RXvbVYivLkyK0IRUkrf4755xzmDJlCnfeeSeLFy+moaGBgw8+GICCgoKPN2zYMAIYwuZpbbtjWRaDgK833aeILCFJnnHQvStKbqT13Oio6QvcAFwStSFO+MQuvNCIryinlCpaybd99NFHefHFF6mvr+enP/0pgwcPbnxqJnBSsveISB5QQnIxbs2TXMzmYjw7HWLsmTJOlMRWdMFzJ1NIPR27yqkHrgLKO3IQEenCJjFumta2O60L3iI2L/qYraqhDb3znHAnSmIturAxpedXWMPndFUJzQAmZXGV0CzgQKCgna+vAr6NtTjsNIEY70xyMW4tZepTNi/6mKOqazpy7FyvfnSiJ/ai20iQ1fAwKaqHx8R2FblRD7895kF2pfWGN01ZjzXwSemlfyDGu7B50cdutG7nJyQX46RXKLnS58OJLxkjurBxxfkG4Hys21cYl4fVWBbHNODyyvLS6hD2mQkMA74DHI014u6B/S7yge5NXleDNdqOrNm2iOSTXIx3pXUxXkgSMR5y+ZPXYQtUmdLRbmpleWm2LeTmNBkluo0ECyHnAJdiZa/d6Fj6WwITmCrgZuBuX7CgD5sWwUazqUn3z4FYpssFYjyU5GKcNHQyaMLt6wu3LWmPd79Fbjh5L/Yfsg2Dendl/YYE73z6JeV/n8Pc5aEuA2zs3exkBxkpuo0E8bkjsUqrr2KisaVu/rOxfrh/A573eFn2ISIFJBVjGbHj/z1SkFcQTqVtZXkpb32yig+XrWHMsP7suE03lq6u4Ws3/5O6htC+VjVA98ry0sz9R3WakdGi25JAhHdh09yqImzmV9O5VdnzgZ0OscMP7929S4++b4rkhbImsOfgXry3xJIqduhTzKzLjgCg9LaXeH9JaMkW64B9KstLfXhllhDX4oitIvBaPwo2x2lGfs9+u2CLgqGI7ntNhLUg36JbDRsSfLYm1KSXBsyJ8O90lhC7MmDHSSHFpGABrVthF246ZRQA02ct4PNwRVeIX6my0wmyytN1nC1QSMiiu033QmaccwB779CHB/79CTf844Mwdw9mr7d7zCJcdJ1cYj22qBoK2/cp5t4JBzJ0QA/ueOEjbnr6w7B23RTF1iWcLMFF18klaghRdB+98FC2692VRauqKS7sws+/MRKAx99ZzH8WhVZHosSn454TAi66Ti4xlxC/89v1tvYRO/TtxoSv7Lzx8dlLqsIU3XzMbidLcNF1con5hLh4XFJWEdau2iIPs9vJEjx7wckZgpTCOVHb0UFme255duGi6+QaLxFiXDfFJLDqSSeLcNF1co0KrMorE6jGytWdLMJF18k1nsNG0mcCVcDzURvhhIuLrpNTBHHdmzEvMs5UAzd7Q6bsw0XXyUVmEP/vfh42FdvJMuL+xXOc0Al6J08nvkUHNcA07/GcnbjoOrnKZdh4pjjyBXB51EY4qcFF18lJgrFMZxA/b7cGm9MX95izs5W46Do5SzCA9G7iI7w1wIzK8tJYjkdywsFF18l1JgJvA7UR21Eb2OFDKLOcrBrX4zhbQ0lZRQ9gFjbQsmsEJtQCHwJjKstLQ51q6cQP93SdnCcQujGYp5nuUEMN8BYuuDmDi67jsFF4D8dyeNMlvDXB8Y5wwc0dPLzgOC0oKasYAzwM9CU188lqsHS1M4LFPCeHcE/XcVoQCOFwrICilvBKhquD/U0Hhrvg5ibu6TpOG5SUVfQFzgEuBXoB3eiYs5LAxLYK6/lwt1ea5TYuuo7TDkrKKvKAI4HjgK8CIzFBbcAm9grWp1exiSx5wGysH+7fgOe9eY0DLrqOs1UEIrwLMAKL+xZhU3trsJlm833ig5MMF13HcZw04gtpjuM4acRF13EcJ4246DqO46QRF13HcZw04qLrOI6TRlx0Hcdx0oiLruM4Thpx0XUcx0kjLrqO4zhpxEXXcRwnjbjoOo7jpBEXXcdxnDTious4jpNG/j/K6/FLHmDitgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# n is the number of vertices in the graph G\n",
    "n = 4\n",
    "E = [(0, 1, 3), (0, 2, 2), (0, 3, 10), (1, 2, 6), (1, 3, 2), (2, 3, 6)]\n",
    "G = nx.Graph()\n",
    "G.add_weighted_edges_from(E)\n",
    "\n",
    "# Print out the generated graph G\n",
    "pos = nx.spring_layout(G)\n",
    "options = {\n",
    "    \"with_labels\": True,\n",
    "    \"font_weight\": \"bold\",\n",
    "    \"font_color\": \"white\",\n",
    "    \"node_size\": 2000,\n",
    "    \"width\": 2\n",
    "}\n",
    "nx.draw_networkx(G, pos, **options)\n",
    "nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=nx.get_edge_attributes(G,'weight'))\n",
    "ax = plt.gca()\n",
    "ax.margins(0.20)\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Encoding Hamiltonian\n",
    "\n",
    "In Paddle Quantum, a Hamiltonian can be input in the form of ``list``. Here we construct the Hamiltonian $H_C$ of Eq. (4) with the replacement in Eq. (5). \n",
    "\n",
    "To save the number of qubits needed, we observe the following fact: it is clear that vertex $n-1$ must always be included in the Hamiltonian cycle, and without loss of generality, we can set $x_{n-1,t} = \\delta_{n-1,t}$ for all $t$ and $x_{i,n-1} = \\delta_{i,n-1}$ for all $i$. **This just means that the overall ordering of the cycle is chosen so that vertex $n-1$ comes last.** This reduces the number of qubits to $(n-1)^2$. We adopt this slight modification of the TSP Hamiltonian in our implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:24:25.956145Z",
     "start_time": "2021-05-17T08:24:25.950463Z"
    }
   },
   "outputs": [],
   "source": [
    "# Construct the Hamiltonian H_C in the form of list\n",
    "A = 20 # Penalty parameter\n",
    "H_C_list = tsp_hamiltonian(G, A, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating the loss function \n",
    "\n",
    "In the [Max-Cut tutorial](./MAXCUT_EN.ipynb), we use a circuit given by QAOA to find the ground state, but we can also use other circuits to solve combinatorial optimization problems. For the TSP, we adopt a parametrized quantum circuit constructed by $U_3(\\vec{\\theta})$ and $\\text{CNOT}$ gates, which we call the [`complex entangled layer`](https://qml.baidu.com/api/paddle_quantum.circuit.uansatz.html).\n",
    "\n",
    "After running the quantum circuit, we ontain the output circuit $|\\vec{\\theta}\\rangle$. From the output state of the circuit we can calculate the objective function, and also the loss function of the TSP:\n",
    "\n",
    "$$\n",
    "L(\\vec{\\theta}) = \\langle\\vec{\\theta}|H_C|\\vec{\\theta}\\rangle.\n",
    "\\tag{6}\n",
    "$$\n",
    "\n",
    "We then use a classical optimization algorithm to minimize this function and find the optimal parameters $\\vec{\\theta}^*$. The following code shows a complete network built with Paddle Quantum and PaddlePaddle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:24:26.790290Z",
     "start_time": "2021-05-17T08:24:26.768068Z"
    }
   },
   "outputs": [],
   "source": [
    "class Net(paddle.nn.Layer):\n",
    "    def __init__(self, g, p, H_ls, dtype=\"float64\",):\n",
    "        super(Net, self).__init__()\n",
    "        self.p = p\n",
    "        self.theta = self.create_parameter(shape=[self.p, (len(g.nodes) - 1) ** 2, 3],\n",
    "                                        default_initializer=paddle.nn.initializer.Uniform(low=0.0, high=2 * PI),\n",
    "                                        dtype=dtype, is_bias=False)\n",
    "        self.H_ls = H_ls\n",
    "        self.num_qubits = (len(g) - 1) ** 2\n",
    "\n",
    "    def forward(self):\n",
    "        # Define a circuit with complex entangled layers\n",
    "        cir = UAnsatz(self.num_qubits)\n",
    "        cir.complex_entangled_layer(self.theta, self.p)\n",
    "        # Run the quantum circuit\n",
    "        cir.run_state_vector()\n",
    "        # Calculate the loss function\n",
    "        loss = cir.expecval(self.H_ls)\n",
    "\n",
    "        return loss, cir"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training the quantum neural network\n",
    "\n",
    "After defining the quantum neural network, we use gradient descent method to update the parameters to minimize the expectation value in Eq. (6). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:24:27.958085Z",
     "start_time": "2021-05-17T08:24:27.952965Z"
    }
   },
   "outputs": [],
   "source": [
    "p = 2       # Number of layers in the quantum circuit\n",
    "ITR = 120   # Number of training iterations\n",
    "LR = 0.5    # Learning rate of the optimization method based on gradient descent\n",
    "SEED = 1000 # Set a global RNG seed "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we optimize the network defined above in PaddlePaddle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:26:08.098742Z",
     "start_time": "2021-05-17T08:24:28.741155Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iter: 10  loss: 46.0238\n",
      "iter: 20  loss: 22.6651\n",
      "iter: 30  loss: 16.6195\n",
      "iter: 40  loss: 14.3719\n",
      "iter: 50  loss: 13.5548\n",
      "iter: 60  loss: 13.1736\n",
      "iter: 70  loss: 13.0661\n",
      "iter: 80  loss: 13.0219\n",
      "iter: 90  loss: 13.0035\n",
      "iter: 100  loss: 13.0032\n",
      "iter: 110  loss: 13.0008\n",
      "iter: 120  loss: 13.0004\n"
     ]
    }
   ],
   "source": [
    "# Fix paddle random seed\n",
    "paddle.seed(SEED)\n",
    "\n",
    "net = Net(G, p, H_C_list)\n",
    "# Use Adam optimizer\n",
    "opt = paddle.optimizer.Adam(learning_rate=LR, parameters=net.parameters())\n",
    "# Gradient descent iteration\n",
    "for itr in range(1, ITR + 1):\n",
    "    # Run the network defined above\n",
    "    loss, cir = net()\n",
    "    # Calculate the gradient and optimize\n",
    "    loss.backward()\n",
    "    opt.minimize(loss)\n",
    "    opt.clear_grad()\n",
    "    if itr % 10 == 0:\n",
    "        print(\"iter:\", itr, \" loss:\", \"%.4f\"% loss.numpy())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that ideally the training network will find the shortest Hamiltonian cycle, and the final loss above would correspond to the total weights of the optimal cycle, i.e. the distance of the optimal path for the salesman. If not, then one should adjust parameters of the parameterized quantum circuits above for better training performance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decoding the quantum solution\n",
    "\n",
    "After obtaining the minimum value of the loss function and the corresponding set of parameters $\\vec{\\theta}^*$, our task has not been completed. In order to obtain an approximate solution to the TSP, it is necessary to decode the solution to the classical optimization problem from the quantum state $|\\vec{\\theta}^*\\rangle$ output by the circuit. Physically, to decode a quantum state, we need to measure it and then calculate the probability distribution of the measurement results, where a measurement result is a bit string that represents an answer for the TSP: \n",
    "\n",
    "$$\n",
    "p(z) = |\\langle z|\\vec{\\theta}^*\\rangle|^2.\n",
    "\\tag{7}\n",
    "$$\n",
    "\n",
    "Usually, the greater the probability of a certain bit string, the greater the probability that it corresponds to an optimal solution of the TSP.\n",
    "\n",
    "Paddle Quantum provides a function to read the probability distribution of the measurement results of the state output by the quantum circuit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:26:08.152206Z",
     "start_time": "2021-05-17T08:26:08.103516Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The reduced bit string form of the walk found: 010001100\n"
     ]
    }
   ],
   "source": [
    "# Repeat the simulated measurement of the circuit output state 1024 times\n",
    "prob_measure = cir.measure(shots=1024)\n",
    "reduced_salesman_walk = max(prob_measure, key=prob_measure.get)\n",
    "print(\"The reduced bit string form of the walk found:\", reduced_salesman_walk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we have slightly modified the TSP Hamiltonian to reduce the number of qubits used, the bit string found above has lost the information for our fixed vertex $n-1$ and the status of other vertices at time $n-1$. So we need to extend the found bit string to include these information.\n",
    "\n",
    "We need to add a $0$ after every $(n-1)$ bits to represent $x_{i,n-1} = 0$ for $i \\in [0, n-2]$. Then at last, we need to add the bit string representation for vertex $n-1$, i.e. '00...01' with $n-1$ 0s to represent $x_{n-1,t} = 0$ for all $t \\in [0,n-2]$. \n",
    "\n",
    "After measurement, we have found the bit string with the highest probability of occurrence, the optimal walk in the form of the bit string. Each qubit contains the information of $x_{i,t}$ defined in Eq. (1). The following code maps the bit string back to the classic solution in the form of `dictionary`, where the `key` represents the vertex labeling and the `value` represents its order, i.e. when it is visited. \n",
    "\n",
    "Also, we have compared it with the solution found by the brute-force algorithm, to verify the correctness of the quantum algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:26:08.169372Z",
     "start_time": "2021-05-17T08:26:08.156656Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The walk found by parameterized quantum circuit: {0: 1, 1: 2, 2: 0, 3: 3} with distance 13\n",
      "The walk found by the brute-force algorithm: {0: 0, 1: 1, 2: 3, 3: 2} with distance 13\n"
     ]
    }
   ],
   "source": [
    "# Optimal walk found by parameterized quantum circuit\n",
    "str_by_vertex = [reduced_salesman_walk[i:i + n - 1] for i in range(0, len(reduced_salesman_walk) + 1, n - 1)]\n",
    "salesman_walk = '0'.join(str_by_vertex) + '0' * (n - 1) + '1'\n",
    "solution = {i:t for i in range(n) for t in range(n) if salesman_walk[i * n + t] == '1'}\n",
    "distance = sum([G[u][v][\"weight\"] if solution[u] == (solution[v] + 1) % n \n",
    "                or solution[v] == (solution[u] + 1) % n else 0\n",
    "                for (u, v) in G.edges])\n",
    "print(\"The walk found by parameterized quantum circuit:\", solution, \"with distance\", distance)\n",
    "\n",
    "# Optimal walk found by brute-force algorithm for comparison\n",
    "salesman_walk_brute_force, distance_brute_force = solve_tsp_brute_force(G)\n",
    "solution_brute_force = {i:salesman_walk_brute_force.index(i) for i in range(n)}\n",
    "print(\"The walk found by the brute-force algorithm:\", solution_brute_force, \"with distance\", distance_brute_force)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we draw the corresponding optimal walk in the form of graph representation suggested to the salesman:\n",
    "* The first number in the vertex represents the city number.\n",
    "* The second number in the vertex represents the order the salesman visits the corresponding city.\n",
    "* The red edges represent the found optimal route for the salesman."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-05-17T08:26:08.431841Z",
     "start_time": "2021-05-17T08:26:08.172882Z"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA1MAAADnCAYAAAD7CwxiAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Z1A+gAAAACXBIWXMAAAsTAAALEwEAmpwYAABjUUlEQVR4nO3dd3xT5RoH8F9Ok+5FKWVWStmIoEBFUURRVIYbxAF6xYviBsWB614nXkFBEBVQUUGR4UYRVIZFFNmyqbSFQoFSuuhOcs7947GU0Za0TXLOSX7fz8dPa2iSN5DmOc/7Pu/zWjRN00BERERERES1oug9ACIiIiIiIjNiMkVERERERFQHTKaIiIiIiIjqgMkUERERERFRHTCZIiIiIiIiqgMmU0RERERERHXAZIqIiIiIiKgOmEwRERERERHVAZMpIiIiIiKiOmAyRUREREREVAdMpoiIiIiIiOqAyRQREREREVEdMJkiIiIiIiKqA6veAyByB1XVsDenGGnZhSi1q7A7VdgCFATbFLSKDUfLmFAoikXvYRIREXkdYySR5zCZIlNSVQ2/7cnGsp1ZWJueg5SsQigWC6yKBRo0aBpgsQAWWOBQNaiahrZx4UhKiEHfDnG4qHUsAwcREfkkxkgi77FomqbpPQgiV+WX2DF/XQZmJqeiqMyB4nInavMGtgAIDQxAWJAVI3sn4uYe8YgKsXlquERERF7DGEnkfUymyBRKyp0Yv3gH5q3LgMUClNrVej9miE2BqgFDe8RjXP+OCAkMcMNIiYiIvIsxkkg/TKbI8P5My8GDczegoMSOUkf9A8Spgq0KIkNsmHZbNyQlxLj98YmIiDyFMZJIX0ymyLDKHE68tGg7Fm7Y75ZZtjMJtikY3K0FnhvUCUFWzsAREZFxMUYSGQOTKTKkojIHhn2wBjsOFnhkpq06wVYFnZpFYvaInggLYn8WIiIyHsZIIuNgMkWGU1TmwODpq5F6pAhlXgwSFYKsChIbhWHhvb0YLIiIyFAYI4mMhYf2kqGUOZwY9sEa3YKEjEFF6pEiDP9wDcocTl3GQEREdCrGSCLjYTJFhvLSou3YcbBAtyBRocyhYntmAV5atEPXcRAREVVgjCQyHq7PkmH8mZYjG2l1DhIVSh0qFm7IwHXnNmMHIz+mqhr25hQjLbsQpXYVdqcKW4CCYJuCVrHhaBkTysMticjjGCPJiBgjuWeKDKKk3Ik+E5cj61iZ3kM5TVxEEFaOvYxnbPgJVdXw255sLNuZhbXpOUjJKoRiscCqWKBBg6YBFgtggQUOVYOqaWgbF46khBj07RCHi1rH+nzgICLvYowko2CMPB2TKTKE577ZigXrMgwz43aiYKuCm5Pi8eK1nfUeCnlQfokd89dlYGZyKorKHCgud6I2H44WAKGBAQgLsmJk70Tc3CMeUSE2Tw2XiPwIYyTpjTGyekymSHf5JXac/+rPuteA1yTIquDPp6/wmV98qlRS7sT4xTswb10GLBa45byWEJsCVQOG9ojHuP4dOWNLRHXGGEl6Yow8MzagIN3N/+cX1MgUC7BgXYbewyA3+zMtB30mLsf8dRkoc6huO/iyxK6izKFi/roM9Jm4HGvTc9zyuETkfxgjSS+Mka7hyhTpSlU1XPDaL4asAz9VXEQQ/njqcp+r9fVHZQ4nXlq0XTZzuyk41CTYpmBwtxZ4blAnBFnNPQNHRN7DGEl6YIysHa5Mka5+25ONojKH3sNwSWGZA6tTj+o9DKqnojIHbpnxBxau906QAKQsYuH6/bh15h+meb8Tkf4YI8nbGCNrj8kU6WrZziwUl5vj0L8SuxPLdmbpPQyqh6IyBwZPX43tBwu8vpG71KFiW2YBBk9fbcpgQUTexxhJ3sQYWTdMpkhXa9NzatUNRk+aBqxN56ybWZU5nBj2wRqkHinSbSN3mUNF6pEiDP9wDcoc5rhAIiL9MEaStzBG1h0P7SXdqKqGlKxCl3/+jSFdcVHrWDQIs6GozIktB/Lw+o+7sO1ggdceY/fhQmiaBovRdwPTaV5atB07Dhbo3hGrzKFie2YBXlq0Ay9fz1bCRFS12sRId8TH1248Bz1axqBpVDDKnSo2ZeRh/OId2H3Y9TjNGGlejJF1x5Up0s3enGIotfjAbR4dgjVpR7Fg3X7kFpejT7s4TB/evVbPWd/HUCwW7D1aXKvnJP39mZYjG2kN0lq41KFi4YYM03cwIiLPqU2MdEd8vCXpLBSU2vHt5kwUljpwWfs4fHzX+Qiyun6pyBhpToyR9cOVKdJNWnYhrLXo+nPLzD+Of392s0h8/1BvNI0KgVWRU7a98RhWxYK07CIkxIa5PG7SV0m5Ew/O3eC1jbSuKrWreOCzDVg59jLTn7FBRO5Xmxjpjvg4aGoytmbKSlaL6BCserIvmkaFoE1cOLZlurbCxRhpPoyR9cdkinRTaleh1bIa/I4LW6JtXAR6tW4IAJiZnOpyoHDHY2gASk1Ux0vAq4t3oKDErvcwqlRQYsf4H3fgxWvNUcpARN5T2xhZ3/i49YSEyfbPapTDqdaqLTtjpPkwRtYfy/xIN3anitqecjagc1MMv6AlWjcKR2ZeCdbvza3189bnMZxOJ7Jz8mC3G/ODh06WX2LH/HUZhildOFWpQ8W8tRnIN2ggIyL91DZGuiM+AkBoYAAm3NQFAPD+qjQcqUUypaoq8guLwSNMzYEx0j14aC/p5octB/HEF5tRWFa7Wawgq4JL2jbCe8O6Q9U0XDpxBQ7klXjlMdTSIhxd/BaKd61GWFgYGjRogOjo6Fp/DQ8P12WD7v79+zF48GDs378fr732GoYNGwYA2Lx5M+bPn4/IyEhcf/31aN++vdfH5gkzk1Pxxk+7DFe+cKIQm4LH+rXHv3sn6j0UIjKQusTI+sbHmLBAzPpXErq2iMZnf+7D019tqdWYK2Jk2d9rEB0dXaf4GB0djcDAwFo9r7swRhqPGWIky/xIN8E2BRa4llAEWRXYnSpUTTq9rNx9BEXlDkQG23BWTKhLwcIdj6EoCsKCA1GqKCgqKkJRURH279/v0ms4UUBAQLVBxJWAY7PZav2cABASEoIpU6bgjTfeOD7ubdu2YdasWXA4HNi3bx8KCwsxbtw4hIaG1uk5jEJVNcxMTjV0kACAEruKGcmpGHFRKyi12ENIRL7N1RjpjtgGSBOLT0acj9aNwjFt+d+YsHRXrcdsUSwIDLCg2OnE0aNHcfRo3Vqlh4aG1phs1RQfIyIi6jxZyRhpPGaIkUymSDetYsNdruc+Lz4ab91yHv5My0F+iR1JCTGIDLYhu7AMWw/kAwBGX94Wo69oh6XbDuGeOevr9BhnEhIWjhU/L0LLhqE4duwY8vLykJubW+uvxcXFHgs0J3694447oCiV1bwNGzZEw4YNERoaiujoaADAZ599BpvNhsmTJ8PhcGDEiBH46aefcN1119VpbEbx255s0xz8V1jmwOrUo7i4TazeQyEig3A1RrojPgLAF6N6oUlUMPbnFiMkMADPD+oEAPhm0wFs3u9ajAwNi8DKlUvQLNKG/Pz8OsXHvLw8FBcXo7i4GAcOHHDxb6uSoiguJV1JSUk477zzEBBQ2dyAMdKYjB4jmUyRblrGhEJ1scr08LEypGUX4eK2sQgLtCKnqByL/srElGUpOPbPh0HFRFR1wceVxzgTVdPQsmEoLBYLIiMjERkZibPOOsul+56ovLwceXl5tQoutQ00QUFBGDZs2EnJVIXc3Fw0aNAAALBhwwYMHjwYAGC1Wo8/D4CTzgspLS2Foii6lV/U1rKdWSguN8dG6BK7E8t2Zhk2UBCR97kaI90RHwGgSVQwAKBFg1CMuKjV8du3Zxa4nEydGCMbNWqERo0auXS/E2mahsLCwjrHx8LCQuTk5CAnp+a22s8++yzOO++8Kv+stjFSVVUUFRUhLCysyphrRIyR7sNkinSjKBa0jQs/qYNQddKyi05q/VqVDk0i4XCqmJmcWufHOJN2jd2z1ykwMBBxcXGIi4ur9X1dDTSapsHpdMJqPf3XvKio6HigyM7OPingZWdnIzIy8rT7fPzxxxg1ahRCQkLqvFcsIiLCa4FmbXqOy32wgqwKxvXviEFdmiI8yIqtB/Lx8g87sCkjz+Xnu7ZrM9x9cSt0bBKJQKuCheszMHbhXy7dV9OAtel1W6UkIt/kaox0R3wEgIRx39dpnCdyR4y0WCyIiIhAREQE4uPja31/u93u0qpYr169TlqVOlFtY2RxcTHOPvtsHDhwAFFRUXWKjw0aNEBQUFCtX29duRoj3REfLRbgkb5tMTQpHjFhgdiTVYjXl+7Cil1HXLq/0WMkkynSVVJCDLZlFtSyQfrpLBbggsSGmJGcio21+AWv7XMkJTT0yGPXbhz1CzTl5eUoLi5GVFQUAOlQWFHOAEhQaNy48fHnAqRDU2FhIQICAlBSUoKSkhJkZmbW+rkVRUFUVFSdNiTXJtCoqoaUrEKXx/X8oE64vWdL7DxUgNV7sjHonGaYPeJ8XDJhOXKLXesi1KFJBJyqhr1Hi9C2cYTLz11h9+HCk1YCiYjcESO9ER8rnscIMdJmsyE2NhaxsXVbxahLjAwKCoLdboeqqsjNzUVubi7S0tJq/dzBwcF1nqyMjIx0ebKyNjHSHfFx1CWtMfqKdsjIKcaivw5i0DlN8f7wHug/JdnlcRg5RjKZIl317RCH+esyUFTPpWZNA7q+uNRNo6paiC0AfTvUfiXJaCrK9M4++2wAQPfu3bFjxw5ccsklSE9PR3R0NJo3b37SfRRFwWOPPYZHH30URUVFVZZWuPK1sLDweKCpC1cDjT24ATTNtXLEhmGBGNI9Hk5Vw+3vr8HRonI4VA03ntcCd16YgMm/pLj0OK8vkc3azw/qVKdkSrFYsPdoMQ+7JKLj3BEjvREfAf+OkTabDQcPHoTD4TgeG2sbH3Nzc1FaWoqDBw/i4MGDtR63xWJxeVXMHhwNVzJ0d8THAMWCkf904rvv0/XYmlmAA3kleLhvW9x7SaLLFRxGjpFMpkhXF7WORViQtd7JlDdEBFnRK1H/Wbf6ePLJJzFv3jzs27cPSUlJePrpp/Hwww9j3Lhx2LNnD1JSUnDHHXecFigqWCwWhIeHIzw8vE6rYicGmrpsTHY10IS07oHYa8ZCCQ4/45jaNY5AoFVBRk4xjhaVAwC27M/Hjee1QKemp5c7eopVsSAtu8iQgYKI9MEY6V31jZFWq7XOq2KapqG4uLjO8bGiKVZeXh7S09NrfC5XY6Q74mPTqGDEhAXCqWrHS1a3/LMHrzYx1sgxkskU6Ur5Z8bCDOccjOydaNi2nK4aP348nnrqKRw7dgxHjhxBbGwsWrZsifvvvx8bN27EZZddhn/9618e29fkjkBT08bjiq9pjmjstdpcKo2JDZdZyKLyyiYkFZtyG0V4r35dA1DqMP4FExF5D2Okd+kZIy0WC8LCwhAWFlZtslYTh8OB/Pz8M8bH3Nxc7NMaItNqPWOMdEd8bBQuP1dir4xvxf88Xm1irJFjJJMp0t3NPeIxsQ7nWXiTqgFDetR+JcZoFEVBgwYN0KBBg5O6EA4YMAADBgzQcWRndmKgadGiRY0/+82mA3j6qy0uzeZmF8psW1hg5cdhWJBsSj5yrKweI64dTdNQbtBT6IlIP4yR3mPmGGm1Wo+3dj8TV2OkO+LjkUL5uRBbACwWKTsNC7LW6jEAY8dIc/RvJJ8WFWLD0B7xCLYa8+0YbFUwNCkeUSF1OyiXvM8WoMDVPaopWcdQ7lDRLDrk+CxclxbRAIAdh87cadJdLBYLAg36O0BE+mGMJHdzNUa6Iz4ezC9FbnE5AhQLzmkedcpjHHN5zEaOkcYcFfmdcf07ItKgH8RRoTaMu7qj3sOgWgi2KbDAtWwqu7AcCzfsR4Biwad3X4Cpt5yHa7s0Q2GZAx//vhcAMLhbC6SPH4gfHrq42se5slNjTBzcBb3/OQejR0IMJg7ugqEuztZaAARbq27TS0T+jTGS3MnVGOmO+OhUteMt+d+5rRveGNIVIy9uBYdTxfRf97g8ZiPHSCZTZAghgQGYdls3BNuM9ZYMtimYdms3hAQa8xeYqtYqNrzGwylP9cJ32/DJ7+mIDQ/ElZ0aY2NGHu74cA1y/tlw68qBl52aRmJw9/jjnfwSGoZhcPd4JCU0cGkMDlVDKwNurCUi/TFGkjvVJka6Iz6+t3IPpixLgVVRcE2XZkjNLsI9c9Zj92HXjzAxcozknikyjKSEGAzu1gIL1+9HqQHqYoOtCgZ3i0ePhBi9h0K11DImFKrmejJV5lDx/Lfb8Py326r88w5NJEF6b2X1s2iTf0lxuY16VVRNQ8uGoXW+PxH5NsZIcpfaxEh3xEdVA978aTfe/Gl37Qd7/DGMGyONNcVBfu+5QZ3QqVkkgnRuCBRkVdCpWSSeG8TSBTNSFAvaxp25LbqrerWOxbebD+CHrYfc9pinatc43JCHERKRcTw3qBM6NY1AkOo48w97EGOkubkzRnojPgLGjpFcmSJDCbIGYHaXAAxen47U6KYos3mvNXXlGBQkNgrD7BE9EWTQ+lw6s6SEGGzLLHCpPfqZ9J+S7IZHqZ7FAiQlmPt8FiLyvKAABbM3fILB6jlIbdgCZVbXDid36xgYI32Cu2Kkp+MjYPwYyZUpMpatWxF27UAs/GQszlaPeb17UbBVwdnNIrHw3l7HW3eSOfXtEIdQk9Txh9gC0LdDnN7DICIj0zTg8ccR9sFMLPziPzg7NoQxkuqMMdJ9mEyRcaSmAldeCeTkIOzqfpj7yi0Y3D3eaxtug20KBnePx9yRFzBImJ3djovW/YKwY3l6j8QlEUFW9Eo07qwbERnAq68Cb7wB2GwImz8Xcx/rxxhJdbNvHy6a8TrCcrP1HolLjB4jmUyRMRw8CPTrJ1/79AHmzUNQSBBevr4zZo/oibiIII/NwAVbFcRFBGH2iJ54+frOLFsws9xc4PXXgcREKLfdipGr5iHY7r2Dd+sixKZgZO9EKIoxa8GJyACmTQOefVbqnebMAa66CkHWAMZIqp3ffwduvlli5MSJGPnHFwh2lus9qhqZIUZaNK0WLa+IPCEnRxKorVuBHj2AX34BIiNP+pGScifG/7gD89ZmQLEAJfb6dzIKsSlQNWBoUjzGXd2RrV3NbPdu4K23gI8+AoqL5bb27ZH/0Bicf+gslBmg81V1gqwK/nz6Ch54SURV+/RTYNgw+X7GDGDkyNN+hDGSqmW3A198AUyeDKxZI7dZrcCQIci//2GcvySXMbKemEyRvgoLgSuukF/wjh2BX38FYmOr/fH8EjsWrMvAjORUFJY5UGJ3ojbvYAs0hJSXIlxz4J4bzseQHjy13bQ0DVi2TALEokWVt/frB4wZA1x1FaAoeP6brZi/LsMQrYRPFWxVcHNSPF68trPeQyEiI1q0CLj+esDplFX3xx+v8cfrHSNVFSGOMoSHBeOefp0YI80sNxeYOROYOhXYv19ua9AAuPde4IEHgBYtAIAx0g2YTJF+ysqAgQNlJaplS2DVquO/3Geiqhp+25ON5buO4M+0o0jJKoRiscCqWKAB0DQNFouc7+1QNaiahnaNw5HUPBJ9nx6FXjvXQPk7BWjd2qMvkTygtBSYO1eSqL/+ktuCgmTmdvRooPPJH7ol5U70mbgcWceMV+7XODIIKx67jDO+RHS6lSuBq6+Wz7ynngLGj3f5rnWOkTnp6PvhG+jVLRHKl1967KWRB1VTqYHRo4Hhw4Gwkw++ZYysPyZTpA+HAxg6FPjyS6BxYyA5GWjbts4Pp6oa9uUUIy27CKUOJ8odKgKtCoKtAWgVG4aWDUMrzycYPlxqzl98EXjuOTe9IPK4w4eBd9+V/7Ky5LbGjWWGbdQooFGjau+6Nj0Hwz9cg1I3lL64S7BNwZwRPXngJRGdbv164LLLgGPH5PPtnXdkv1QduRwjMzNlUtNmAw4dkpUMMr7qKjWuuEIqNa6+GlCq31PHGFk/TKbI+1QV+Pe/gVmzgOhoYMUKoGtX7z3/jz8C/fvLTM2OHfUKUOQFf/0lAeLTT4HyfzbKnnuuBIihQ2VVygXPfr0FC9fvN0QpQ7BVumK9fL2xSxeISAc7dwK9ewPZ2cAtt8jkX4AXZ+avuEIqRmbOlFhNxlXLSo2aMEbWHZMp8i5NAx57DJg0CQgJAX7+GejVy7tjcDiA5s1ldWPtWml6QcaiqsAPP8j7ZNkyuc1iAa65RpKoPn1qnQSXOZy4deYf2JZZoOtm26B/zmmZO/ICdsUiopPt3QtcfLHscRkwAPj6a1kl8qaPPgLuuks+Z1es8O5zk2tqqtS4914grvZnMjFG1h2TKfKul1+W0jqbDfjuO2kSoIdHHgGmTJGZm0mT9BkDna6wEPj4Y6n3TkmR28LCgBEjgIcfBtq0qdfDF5U5MHj6aqQeKdIlWARZFSQ2CuOBl0R0usOHJZH6+29ZmfrxRyA01PvjKCiQC/PSUmDfPiA+3vtjoKpVVanRtatMMt5yi8uVGtVhjKwbJlPkPW+/DTz0kNTtfv45MGSIfmP580+gZ0+gSRMgI0PahJJ+MjLk/TFjBpCXJ7eddZYkUHffLeWgblJU5sDwD9dge2aBV8sZgq0KOjWLxOwRPU0VJIjIC/LygEsvBTZvBs47D1i+HIiK0m88N98MLFgA/O9/wBNP6DcO8kilRk0YI2uPyRR5x5w50vgBMEYdtqbJnqmUFGDJEuDKK/Udj79as0YCxMKF0voXAC68UALEDTd4LMktczjx0pebsHDtPpRaAz3yHCcKtikY3C0ezw3qaJqyBSLykuJiiUG//Qa0aycNmepQpuVW334LXHcdcM45lXtxyLuKiqTk8tRKjbvukonGejTtOpMyhxMv/W8BFuYGotRWv9UuV5g9RjKZIs/79lvgxhvlYnnCBGDsWL1HJF54Afjvf4E77pDSMvIOh0O6OE6eLKexA7K5esgQKbvs2dM747j7bqxd+gceGPIcCsKiPDIDF2xVEBliw7TbuiHJBB2JiMjLysslafnxRymnW7VKVuX1Vl4ONG0K5ORIMnXOOXqPyH9UV6nx0EMyEe3GSo1q7d0LdO6MtdFn4YG7/ocCLYAxsgZMpsizVqyQlpxlZcC4ccCrr+o9okp//y0zO+HhUquuR226P8nLA95/Xw4Q3LdPbouOrjxA0Jt1+UuWyPsyKAgl6zZgfKqKeWszoFiAEje0hg2xKVA1YGhSPMZd3dHwZ2QQkQ6cTuDWW6WcrlEjWZFq317vUVUaNQqYPh148kngtdf0Ho3v06lS4zSaJvvZf/oJGDIEJXPmYvyPOxgja8Bkijxn3To5J6OwELjvPmDaNOO1Ie/ZU/ZPff65tNkm9/v7bylTmDVLyhYAKWV55BHgzjtPO0DQ4woKpF1sRoZcIDz5JAAgv8SOBesyMCM5FYVlDpTYnajNp6PFAoTYAhAeZMU9vRMxpEc8okK83IWLiMxB02QiaeZMIDJSJh7PO0/vUZ0sORm45BKZ6EpPr/GcIqojo1RqnOjDD2WvcsOGwLZt0owEjJE1YTJFnrF9u3wIHz0qM29z5hjzg3jqVKk9HjRIuguSe2iaXBxMmiQHCFZ8zFx+ucyy9e+v3/vh/vulnWyPHhK8TpntU1UNv+3JxvJdR/Bn2lGkZBVCsVhgVSzQAGiaBovFAgsAh6pB1TS0axyOpISG6NshDr0SG0JRDDZpQETG8uSTwOuvA8HBwNKl0r3PaFQVSEyUkq8VK6TRAblHdZUa99wDPPigfh0UDxwAzj4byM+XjoG33XbajzBGno7JFLlferq0dz1wABg4EPjqK++fk+GqrCygWTOZMjl4EIiN1XtE5lZWJqt8kycDmzbJbYGBwO23yyxbly46Dg7SIatvX3k/rl/v0j4AVdWwL6cYadlFKHU4Ue5QEWhVEGwNQKvYMLRsGAqL0VZcici4XntNyt6tVuCbb+Q8KaN6+mlg/Hhg5EjZw0P1U1WlRtu2lZUa4eH6jU3TgGuvlQnQa66R96YLsY0xkskUuduhQzLDpvc5GbXRv7+M8513pByRai8rC3jvPfk7PHxYbouLk1WgUaOOlwnoqqhIkrnUVGk+8vzzeo+IiPzN9OnymWixAJ99JmcDGdm2bVIWHR0t8b2e5xj5peoqNfr2lUqNAQOMUbnz6afAsGHSkn/7dploJpcwmSL3yc2VczL++gvo1k3OQ9DznAxXVXyA9OolrWnJdVu3yirUnDmyKgVIwlJxgGBwsK7DO8mYMTLWLl2AtWtlxYyIyFs+/1zKpjRNSo1HjdJ7RK457zypNPjyS2mEQK4xeqXGiQ4fBjp1ku6NH34o7dfJZUymyD2KioB+/WQPSvv2snG1USO9R+WawkJZOSkullWLVq30HpGxqaqs5E2aBPz8s9xmsci+s9GjpemI0Zb0f/tNVkoVRRqOdOum94iIyJ/88IO0QHc4pKvtuHF6j8h1EycCjz8O3HSTdJqjmpmhUuNUgwcDX3whXfwWLzZeDDc4JlNUf2VlUme7dKmxzsmojdtvl5KLl18GnnlG79EYU1ER8MknUu+9a5fcFhoqM1iPPOLRAwTrpaQEOPdcYPduqf9/5RW9R0RE/iQ5WQ7lLS2VpOR//zPXxeqBAxLbAwMlOTBDxYkeqqrUOOccqYq49VZjVWqcaOFC6R4YHi5lnWa7fjMAJlNUP6eek7FqlbS9NpsffpBmGR06SK2wmQKdp+3fL23tp0+XUk5AAmvFAYINGug7vjN56im5eOnYEdiwwbgBjYh8z8aNUv5eUCBNHKZPN2d86dtXGvh88AEwYoTeozGOqio1AKnUGDPGmJUaJ8rOlu59WVnmKj01GCZTVHeaJsHhgw+Me06Gq+x2oHlz4MgR6fLGMjDZVzRpkiTKDofc1rOnBIgbbzRuh8YTrV0LXHCBfL96tT5ndhCRf9q1S8qLjxyRmf+5c+UMITOqOHvosstkP7S/q6lS4+GHzTOpXFGVc+mlwC+/GKMRhgnxb43qRtOAJ56QRCokBPj+e/MmUoAkBhWH9n76qb5j0ZPDIUv+F10EnH++BH9NA26+WfbD/fGH/D2ZIZEqK5PApqqSADKRIiJv2bdP9hEfOSL7UObMMW8iBch+qaAgmTQ9cEDv0ehn/37Z7xYfL3ugdu0CWrSQ6of9+4G33zZPIvXtt5JIhYbKmVdMpOqMf3NUN6+9JptSrVa5+L74Yr1HVH+33y5f586V8kV/kp8PvPEG0KaNzKCuXi118Y8/Lk055s2rXOExi1dflfrvNm2AF1/UezRE5C+ysiSRysiQiakvvjB/99CoKCld0zSJkf5m7VrpxNiqlVz/5ObKBN3nn0uMfOIJ45e8nygvr7Kk79VXgdatdR2O2bHMj2rv3XdlRsZikQ/VihUds9M0aaKwZw/w00/AFVfoPSLP27MHmDJFSjgKC+W2Nm2kocS//qXvAYL1sWkTkJQkK22//iqlNkREnpafL6VwGzcCXbvKSk50tN6jco+vv5bW6F27Vrb69mUOh7zmSZNkghGQ1ZubbpJqhwsv1HV49TJihBwc3KuXxEgzr5oaAFemqHbmzgUeeEC+f+8930mkAEkOK1anfLnUT9OAlSslKLZtK8lUYaFcAHz7rZQtPPigeRMpu10ChcMhr4OJFBF5Q3ExcM01kki1aQMsWeI7iRQgB9xHRwObN8uqv6/KzwfefPP0So2xY2UVav58cydSS5ZIIhUUJBOpTKTqjckUue7774E77pCL8ddeA+65R+8RuV9FMvXFF9JS25eUlwOzZwPdu8tm06+/lr1P//qXBP9ly+RCwOx10xMmyOtp2RIYP17v0RCRPygvlwvv5GRpZvTzz8Y8T6g+goLkNQK+OeG4Z49UZbRoATz2GLB3ryRUU6fKfqgJEySumFlFV0lAyt/bt9d3PD6CZX7kml9/lU20paVSG/y//+k9Is9JSgLWrZPZp4rAYWbZ2bKKOG0acOiQ3NaoEXDfffJfkyb6js+dtm2TTozl5f5TqklE+nI6gWHDZP9MbKzEy44d9R6VZ6xcKZNxLVvKKo3ZJ980Tf69Jk8GvvlG/h+QSo3Ro+XIFF9aubnvPrkeSEqSFTerVe8R+QQmU3RmGzbIB0tBgaxGvfeesc9NqK+33pIP0WuvlQ9Xs9q2rfIAwdJSua1zZ6n1vu023ztvyemU+u8//5SZtxkz9B4REfk6TZM9xO+9B0REyFlM3bvrPSrPUVUgIUGaa5h5P2p5uTRWmjRJKhkAaRJy660S/889V8/Recby5XJemM0m13WdO+s9Ip9h8ikF8ridO2VFqqBA2mO/845vJ1KA7ANTFGDxYiAnR+/R1E7FAYJXXSUflO+/L4nUgAGyUvPXX7KfyNcSKUASxz//lBKbCRP0Hg0R+YNnnpFEKihI9pz6ciIFSGy87Tb53oylftnZwMsvy8raHXdIItWoEfD881LW99FHvplIFRUB//63fP/cc0yk3IwrU1S9ffukrev+/cDVV8sqjdnbu7rqqquApUslSN57r96jObPiYtkPNXmyJMCAnB1x551SA+7rddG7d0uHqdJS2ds3YIDeIyIiXzdhgpS9BwQAX30le079wZYtQJcu0gr80CFzXBdUV6kxerTslfbFCcYTjR4tVTddu0qbdzOcFWkiTKaoallZsny/e7ckVEuXysW5v5g9W2atLr5YNhQb1YEDshdq+vTKVbTmzYGHHpJSt5gYfcfnDaoK9OkDrFol/2Yff6z3iIjI182cKWXvFovEi4rmRf6ia1epdPj6a+C66/QeTdU0TTrXTZok1zAVBgyQcvfLL/f9ShsA+O03uZ5TFEmkzjtP7xH5HO48o9Pl5cnKzO7dsty9aJF/JVIAcP31QEiIXKDv3Wu8Dj7r10uAmDdPWoADsqF0zBhg8GD/mnV65x35d2rcWP5OiIg8acGCyoqFqVP9L5EC5DX/9ZeU+hktmaqo1HjrLWDHDrktJEQ61z78MNChg67D86qSEint1zTgqaeYSHkIV6boZMXFkkitWiVnECUn+157V1fdeqt0Z3r1VWDcOL1HIw0WvvlGEoZVq+Q2RQFuvLHyAEF/mGU7UVoacM45Ug/+5ZdydhYRkaf8+KM0J7LbgZdeAp59Vu8R6SMjQyYZg4KAw4eByEi9R1R9pcaDD8oqoj9UapzqySeB11+X7pIbN8q/F7kdkymqVF4uKzKLF8s5C6tWGW9FxpsWLZIa+E6dgK1b9UtUCgqADz6Qw3XT0+W2yEgp43vwQems5I80TVqfL1smTUM+/1zvERGRL/vtN6BfP5ntf/RRYOJE/5vAOtGll0qr9FmzZNVHL6zUqNratcAFF8j3q1cDPXvqOx4fxmSKhNMpy/bz5sk5GcnJ/rUUXhW7HWjaFDh6VGZ0vN3hJy1NEqgPPgCOHZPbEhOlocRdd0kbXn9WsWchNhbYvl06MhERecLmzbI3Mz9fyqbef9+/EylA/g5GjpS9Rz//7N3nrqlSY/RoOSbDn/99ysqks+S2bcDYsexw62FMpkhm+EeNknN5/OGcjNp44AHZk+OtDyNNk8AwaZIEClWV2/v0kVm2QYN86wDBusrIAM4+W5LMuXOBW27Re0RE5KtSUqQZUVaWXKzPm8fDTgHZX924sUw87t8PNGvm+eesrlLj3/+Wxkv+WqlxqueflzLUtm1lIiAkRO8R+TQmUyT7gV57TVqD/vijXLiTWL1auhk2by6NKDyVyJSXA/PnS+vW9evlNptN9m098gjQrZtnnteMNE1OpV+8WMpSv/zSv2cgichz9u+XGLBvn5T4ffcd952c6MYbpS38G29I6aOnsFLDdZs2SZmj0yllmGY9WNlEmEz5u9dflw2KVqt8IA4apPeIjEXTgNat5YP8l1/k9HB3OnpUNstOmwZkZsptsbGyUnj//VJmSCf75BM5Pys6Wsr7+HdERJ6QnS0Xojt3yt6Tn34CwsP1HpWxfPklcNNN0iVuwwb3PnZNlRqjR8ueZlZqnMxul71RGzfKSt2UKXqPyC8oeg+AdDRjhiRSFouczcNE6nQWS2XbW3ee9r5jh7TWjY8HnnlGEqmzz5Z9QPv2yfI8k4TTHTwoM5GArOLx74iIPKGgQA6r37lTOob+8AMTqaoMGABERcnFe0Ub8voqL5d4m5QEXHKJTPQGBADDh0vlxooVUpXAROp0EybIv0VCgnQiJq/gypS/mjdPSsg0TfYE3Xef3iMyrp07pa1oZKS0gK3rSemaJgcHTp4s5ZQV+veXWbZ+/ViuVhNNk5KSr7+Wv7Pvv+ffFxG5X0mJfMasXCmVCcnJnLipyb//LeV3zzwDvPxy3R+nqkqNhg3l+oSVGme2bZtsCSgvl4Ygl1+u94j8BpMpf3TokNQal5TIB98zz+g9IuPr3l1KGBYulJKG2igpAebMkSRq+3a5LSQEuOMOWWXp2NHtw/VJ8+ZJo4mICAka8fF6j4iIfI2mydlRr74qDRVWrQJatdJ7VMa2fLmUwCckAKmptZ/k2rFD4uPs2RIvATmSZPRoYNgwNk9whdMpHQz//FO63E6frveI/AqTKX9UVASsWSOrJOPHc3bfFZMmyeba66+XkgNXHDwoM2zvvSczboAE54oDBBs29Nhwfc6RIxJcs7MlSNxzj94jIiJfVVQk+1afekrKr6lmqipnUu7fL8nnRRed+T7VVWpcfbV0rmWlRu288YZ0HW7RQs7FjIrSe0R+hcmUD0tNTUVAQABaVnXwbnm5dIvjh5VrDh6UDymrVVb2GjSo/mc3bJAA8fnnshkUkJWtMWOAIUOAwECvDNmn3HKLrExdfrlsAuf7lojqocb4CMhMP/fkuO6JJ2S/zn33ydaB6rBSw/127wa6dgVKS2VvX//+eo/I7zCZ8lHTpk3DwoULceTIEQwbNgwPP/wwQkND9R6WufXrJ3XIM2bIQYUncjqlZe6kScCvv8ptiiIrWWPGyEwdE4C6+eor2SsVGiozbiy5IaJ6YHz0gM2b5WD7hg1lv9Opk4ZVVWo0bSqVGvfey0qNulJV6W64apV0uf3oI71H5JfYzc8HffHFF5gxYwa++OILfP755/j5558xf/58vYdlfsOGydc5cypvO3YMeOstoF074IYbJJGKiJAE6u+/gS++kMMemUjVTU6ObDwG5Cw0JlJEVA+Mjx7SpQvQubMkSkuWVN6+caOsOrVsCbzyivx59+4SR9PTgaefZiJVH++8I4lUkybAm2/qPRq/xSO8fYymacjIyMDTTz+NmJgYxMTE4KGHHsKvFaslVHc33CB19L/+Cvz2m5yv8f770kIXkAv9hx8GRoyQzn9Uf2PGSFnlxRcDDzyg92iIyMQYHz2o4hiRceMkUXI6T6/UuPFGaSrBCUb3SEuTfX0A8O67QEyMvuPxY0ymfIzFYsHdd9+NiupNTdMQHByMLVu2HP+ZgwcPoilbjFbL4XDAaq3iVyMiQrrlLFsmBzlWVMj27i0X/ddeyxp7d/rhBzmgNzhY2u4qXEgnorpjfKy/auMjIIfojhsHLFgAVKz2RUQAd98tE42sLHAfTZOW9EVFsqf4+uv1HpFfYzLlgyIiIo5/b7FY0KpVK4SFhQEAxo0bh+DgYPznP//Ra3iGtW3bNrz55ptQFAXDhw/HJZdcUvmHDgdw882SSAHyQTZsmMyyde+uy3h9Wn6+1NEDcoBxu3b6joeIfALjY93UGB81Ddi1SyYbK/4/NlaOXWGlhme8/75cj8TGAlOm6D0av8epXj/QvHlzhIeHY8yYMVi9ejWeeOIJvYdkOG+++SaGDBmCs88+GxdddBHGjh2LAwcOVP6AqkrL1gYNKs+8ePxxJlKe8vjj0mb3/PNl1Y+IyAMYH8/sjPHRYpE9UTExQJs2ctu558pkIxMp98vIAB57TL5/+22gUSN9x0Ps5udzNO2kWmRN05CXl4fWrVvjrLPOwvLly9GgprbefiorKwsNGjSAzWYDAFx11VV477330OrEsgSHQ1rKP/aYdCR64gngf//TacQ+7OefpXNiYKC0mec5L0TkLqp6vGSY8dE1LsVHux3IzZXjQ5o0kT1TBw7I9+Q+mgYMHAgsXiz7uL/4gvvPDIArU75E06T1aFHR8ZssFgsaNGiAV155Bd9++y0DRTXi4uJgs9mwatUqJCQkID8/H9999x3Ky8srf8hqlfbct98u///ZZxKYyX0KCyvbzj//PBMpInKfv/+WyZrCQgCMj65yKT7abEBcnKxODRggsfHzz/UbtK+aPVsSqQYN5HqPiZQhcGXKlzz7rLQe7dNHAsYJm0Q1TYOFv3RntGvXLmzfvh19+vTB2LFj0aFDB4wdOxbKic0PVBVo3Vraui5fDlx6qV7D9T0PPSRlC+edB6xZIwGaiKi+DhyQLnL79gE//ghcccXxC1HGR9e4FB8BYOFCOaC+e3dg3Tp9BuuLDh4EOnUC8vKAjz+WlvNkCFyZ8hVvvCGJVEAA8OijJyVSABgoTnXkiJQlnKJ9+/a44YYbEBMTg6uuugpbt25FWVnZyT+kKMBtt8mqyal/RnWXnCyJlNUKfPghEykico+jR4Err5QJsB49gAsuOGlGn/HxFJomB+86HCfd7FJ8BIBBg2SVqlWrkyplqB40DbjvPkmkBgwAhg/Xe0R0AiZTvuCDD4CxY+X7jz6SFt1UtU2bgH/9C2jRAli9usYyvby8PERFRSGkouHEif7zH1k54aqUexQXS9cnQFrrnnuursMhIh9x7BjQvz+wfbtMgP3wg7TrptOVlsr1RJcusnJ3YhnfKWqMj8HB0iThgw+AfzolUj3Nnw9884009Jg+neV9BsPW6Ga3cCFwzz3y/ZQp0q6bTuZ0At9/LwcIrlght1ks0lb0ootOOr/oyJEjmDt3LubNm4eAgABMmDCh6scMDJT/yD2ef172M3TuLOWqRET1VVoKXHcdsHatrJIsXQo0bKj3qIzn0CHgnXeksdKRI3JbkyayohcaevzHXI6PAGOkOx05Ajz4oHw/caJMBpOhMJkys6VLpdxMVYEXXpD9JlSpsBCYNQt46y1gzx65LTy88gDBxMTT7hIeHg4AGD9+/MnnaJDn/PGHJLqKIuV9DMBEVF8Ohxxmuny5JAY//QQ0a6b3qIxl0yZg8mRg7tzKVajzzpPjKIYOPe2zmPFRJw89BGRnA5dfLgf1kuGwAYVZrV4t7aOLi+Ushzff5LJvhb17Ze/NzJly+CsgZ2A8/LAkUlFR+o6PKpWVSfDesYOt5onIPVQVuOsu4JNPpOvZypXAOefoPSpjqK5S47rrJInq3ZvXEkby1VfAjTdKueSWLbLCSobDlSkz+usvOWeguFj2/7zxBj/8AOD33yVAfPmlBAxAyvjGjJFAYfXs2728vByZmZnYtm0bsrKycMstt1RdT06VJk+WRKp9e+C//9V7NERkdpomn/mffCIXoD/8wEQKqL5SY8QImWhs3dqjT8/4WAdFRcD998v3r73GRMrAuDJlNn//Le1dDx+WA9vmz/d4kmBodrscWjd5sjSEAOTv4+abZcUuKckrw/jll1/w+uuvo7i4GA6HA7169UJmZiZuu+02XHPNNV4Zg+moqkwIPPoocOedkvgSEdXHf/8rZe+BgbICc8UVeo9IX/v2AVOn6lqpwfhYR6WlMnn+5ptyruWpLejJMJhMmcmBA3LBuXev1M4uWiRdc/xRbq4Eh6lTgf375baYGODee2Umx4sbNJ999ll8//33OPfccxEcHIxLL70UQ4cOxZw5czBr1iz88ssvXhuLKZWVAUFBeo+CiMzurbdkEk1RgAULpDzKX+lcqVGB8bGeHA55PzORMjQ/XtIwmexs2SO1dy/Qsyfw9df+mUjt3i0B86OPZFUDkBKx0aPlALsTOg95w86dO5GWloaNGzcCkG5HAwcOxNChQzFs2DBMnToV+fn5iOI+reoxkSKi+vr4Y4kDAPD++/6ZSFVXqXHrrZJEealSowLjoxv4c+WRifBfyQyOHZND2nbskNbRP/wgtc7+QtOkjfnkybIaV6FfPwkQV12l26xNixYtsH79ehT/k9itXLkSrVu3RnZ2NmJjYzFr1iwE+XmykJ6ejqVLl0LTNFx55ZVoxbpvInKnr7+WkjVASqLuukvX4XhdVZUaDRpIpcYDD+jWSpvx8cwYH30Dy/yMrrRUEqnly6WVd3Ky/7R3LS2Vlq2TJ0vdMCCrGMOGyQxk5856ju64UaNGIT8/H507d8bmzZtx5513YuDAgVBVFQqX5tGzZ0/06dMHW7ZsQUxMDN5++200aNBA72ERkS/45ReJkeXlwHPPAS++qPeIvKemSo3hww1xYC7jY80YH30Dkykjs9uBwYOBb78FmjYFVq2q8mwkn3P4MPDuu/JfVpbc1rixzLCNGgU0aqTv+E6Rk5ODlJQULF26FF27dsWAAQMQEBAACzss4tVXX8XGjRuxYMECAMDdd9+Ntm3b4qmnntJ5ZERkemvWyP7hoiI51HTKFN/vbFtdpcYVV0ilxtVXG2p/DeNj9RgffQeTKaNSVWl7Pnu2LNf/+qthVmI85q+/JEB8+mnlAYLnnlt5gKDRywGcTqCkRGYDGSjgdDoxefJknHvuubj88ssBAMuXL8fLL7+MJUuWwGq1YsmSJbjssssQyIN6iag2tm4F+vQBcnKkWuHjjw2VRLidSSo1alRcLF0WuQ+I8dHHMJkyIk0DHnlE6p/DwqSMoWdPvUflGaoqe8AmTZLZNkASkWuukSSqTx9zJCaaJofrTZkiZSY8HR4AUFpaivLyckRGRh6/7eqrr8Z3332HGTNmIDk5GZ9//rmOIyQi00lNlSNCDh6UWPHFF4DNpveoPKOmSo177wXi4vQdn6uOHZO29Tt2SMwnxkcfwukBI/rvfyWRCgwEvvnGNxOpwkKZSXzrLSAlRW4LC6s8QLBNG33HV1sWC7B2LbBypaysMZkCAAQHByP4n66TdrsdNpsN7du3x4svvoiff/4Zc+bM0XmERGQqBw9K86GDB4FLL5WzFn0xkaqqUqNrV5lkvOUW41dqnMpqlSYZx45JzG/bVu8R6Y7x0Xf48Jq4SU2eLCsbigJ8/rnUg/uSjAzgySeB+HipcU9JAc46C5g4UboQTZlivkSqwu23y9cFCyqDHx1n++eCp3379njllVdw1113oXXr1jqPiohMIycHuPJKWZnq0UMmG33piBBVlX1Ql18uidOsWbJ3+tprpQnVxo1ywLnZEikACAmpbFf/6af6jsWAGB/NjWV+RvLRR5UtXWfNkj1TvmLNGinlW7iw8gDBCy+UWbYbbvCdGuquXWVG8euv5WBEf6dpUusfEnL8pqNHj2LSpEl4+eWXdRwYEZlKYaE0WVizBujYUfYRx8bqPSr3qK5S4667pFLDV1ZxfvpJkuE2baQToRlK+D3N4ZBron8SZMZHc2IyZRRffSWd+1RVko6KwwfNzOGQ09cnTQL++ENuCwgAhgyR1+eL5YsTJgBPPCH/lv906PFr774rXSjfe0/ORvsneLItLhG5rKwMGDhQ9g+3bCmfKTqdneRWGRnA228DM2YAeXly21lnAQ89BPz730B0tJ6jcz+nU/7dDh2SawJfvAaojdJSWYV88knpwvhPownGR/NhMmUEP/8sgaK8HHj+eeCFF/QeUf3k5ckJ9FOnAvv2yW3R0ZUHCMbH6zk6z9q/X4JhYKBsHPbnk9337pUOU4WF0t7/mmv0HhERmY3DId1cv/xSGi+sWmXeUvAK/lKpUZVHH5XX/tBDUtbvz555Bnj1VTkb7K+/jidTZD5MpvR24jkZDz0ky/xmXfr++28Z/6xZ8noAoF076Ux4552GOEDQKy67DFixAvjww8qyTX+jaTLTtnQpcNNNctFARFQbqiorNLNmyYTcihVSSm1GFZUakycDv/8ut/l6pUZV1q+X/W6NGgEHDvhm8xBXbNgAnH++vMdXrQJ69dJ7RFQPXEfU09atQP/+kngMHy4fsmZLpDRNNsZee60kTm+/La/n8stlI+2OHcD99/tPIgXIuR8A4M+deGbNkkQqJgaYNk3v0RCR2WgaMHasfJaEhgLff2/ORCovTxostW4tK2y//y6J4RNPAGlpcnaUvyRSANCtG9ChA3DkiFTl+KPycplodTplspmJlOlxZUovJ56Tce21MnNvphmasjLpNjh5MrBpk9wWFCQd7R55BOjSRc/R6SsvT8pR7HapiW/eXO8RedeBA8DZZwP5+ZJQVnQ5JCJy1UsvSdm7zQZ89x1w1VV6j6h2qqrUaNtWVqHuuEP2kPqrl18GnntOYoM/Tjq++CLwn/8AiYlS3udPk80+ismUHjIzJZFKS5OSsB9+ME9716wsaSbwzjuyJwiQQwPvvx+47z7zHCDoaTfdJCUdEycCjz2m92i8R9NkcmDRImDQINkrZbbVViLS19tvS9l7xREhQ4boPSLXaJqUIk6aJJ+BFZdXl18uSdSAAfKa/F1qqqzUhYXJdYQ/JRNbtgDdu8tk6/LlclYamR5/q72t4pyMtDQgKck852Rs2QLcfbc0V/jPf+QDsEsXmXXbu1duYyJVqWI1xt/O05g7Vy4ioqIk6WYiRUS1MWeOJFIAMH26ORKpsjJpbd6tG9C3r6yk2WxSyrV5s5SzDRrERKpCYqI03Cgqkmsgf+FwACNGSCJ1331MpHwIV6a86cRzMjp1knMyGjbUe1TVU1Xgxx9llq2ittlikaAwerSsqvFiuWqlpUDTplLyt22b/Hv7usOH5XXm5AAffCBBg4jIVd9+Kwe7Op1yzMTYsXqPqGY1VWqMGiXl3lS1d96R7r79+0t1jj/43/+Ap56SSemtW4GICL1HRG7CZMpbSkslCfnlFyAhQbq3GHUvTVER8MknUu+9a5fcFhoqs2yPPOI7Bwh62siR0iL+6aeBV17RezSeN2SI7P3r1w9YsoSJNhG5bsUK6QBaVmb8z8ytW2W/8Jw5Ml4AOOccaW1+663mqDbRW3a2TDhqmmx98PXKlp07gXPPlffLjz+abw8g1YjJlDc4HHKh+fXXxj4nY/9+6bw2fTqQmyu3xcdXHiDYoIG+4zObFStk9S4hAdizx7dLPBYulPd4eLhcaLRsqfeIiMgs1q2Tz8rCQil/mjbNeJMxVVVqADJJOmYMKzXqYtAg6dI4dSrw4IN6j8ZznE6gd2/p5DhihFRukE9hMuVpqip7jT76SNqhrlxpvE53a9dKgFiwQBI/QFq1jhkjJRdm6jJoJKoqScX+/UBysjQd8UXZ2dK9LytLSjfuu0/vERGRWWzfDlxyCXD0qKzqzJljrImnmio1Hn5YjgShuvn8c/k379kT+OMPvUfjOZMny/VU06byfo+O1ntE5GZMpjxJ0+S078mT5cP3559l06UROByyUjZpErB6tdwWECBd6MaMAS64QNfh+YwnnwRef13q5999V+/ReMawYdJoo08fYNkyY10IEZFxpafLJNOBA8DAgcBXXxln8q6qSo0WLaRSY+RIVmq4Q3GxVOsUFgIpKcas2KmvPXukBLSkRPYEXnON3iMiD+BVjye99JIkUjabJC5GSKTy84E33pAPrSFDJJGKigIef1zalc6bx0TKnSq6+s2fLwf1+ZrvvpNEKiRE9ocxkSIiVxw6JPsrDxyQEqj5842RSK1dC9x2G9CqFfDaa5JI9ewpqyipqXLYLhMp9wgNBW64Qb7/7DN9x+IJqipbJEpK5FqAiZTP4sqUp0ydKiUAiiJB4qab9B3Pnj3AlCnAhx/KLBAgCdUjjwD/+pd/HyDoaeecI/uIfG1WKi9PyvsyM2WFc/RovUdERGaQmyttof/6S9qJL1smk3p6qapSQ1EqKzWMMBHqq5YskcYj7dpJkwZf2nf27rvS2TEuTsr7jNy9meqFyZQnzJ4tJ5wD+raI1jRpvz5pklzIV/xTX3aZBIiBA7mS4A0V7VBvvllW/nzF3XdLcn7hhbInLCBA7xERkdEVFcmK1O+/A+3by2dHo0b6jCU/X1bUp06V8xIBSepGjpSGCGyk43kOh5RPHj4M/PmnnL/pC/buBTp3lsnrBQuAwYP1HhF5EJMpd/vmG5nNcjqBiROBxx7z/hjKy+WifdIkYONGuS0wUEoXHnlE2nOS9+zbJ0E5OFgCRmSk3iOqv6VLpbVrUBCwaRPQoYPeIyIioysrA669Vj4/4uOB336Tr97GSg1jGT1aGnw88ohsjTA7TZPVtqVLJYlasEDvEZGHMZlyp+XL5QC6sjLgmWeAl1/27vNnZ8sBgtOmST06IDN+990n/zVp4t3xUKU+fWSV8KOPgDvv1Hs09XPsmMy47dsnewqefFLvERGR0TmdwC23yDEKjRrJESHe7IRXUakxebJMep5YqTF6tFRqcHVdH2vXAuefL80o9u8HrFa9R1Q/H34olRsxMVLex8ObfR6TKXdZuxbo21dmuR54QMoGvFX7u21b5QGCpaVyW+fOUsp32208QNAIZswA7r0XuOIK4Kef9B5N/dx/v9SCd+8u7WzNHviIyLM0TUrnPvhAVuZXrADOO887z11dpcatt0oSxUoN/WmalHympJj/QNsDB2QvcX6+XJNVNKEin8Zkyh22b5duRDk5krzMnu35vUiqKkvIkybJ1woDB0qAuPxy39rIaXa5ubIy6HDIzFvTpnqPqG4qDiK22YD166W5BhFRdTRNOuBNnChdP5cu9c6Ze6zUMJcXXwT+8x9g+HA518uMNE3KWBctkmZT33zD6zA/4TfJlKpq2JtTjLTsQpTaVdidKmwBCoJtClrFhqNlTCgUpQ5v+rQ0CQyZmXKa95dfera9a3GxJGuTJ0vnG0Dai955p9Qbt2/vueem+rnhBukY9eabsmpoNkVFcuB0airwwgvA88/rPSIicgOPxUcAGD8eePppWcH+5htgwAD3Dv5U1VVqjB4tqwSs1DCmv/8G2raV/WqHD8t1jdl8+qmcuxgVJe/D5s31HhF5ic8mU6qq4bc92Vi2Mwtr03OQklUIxWKBVbFAgwZNkwkDCyxwqBpUTUPbuHAkJcSgb4c4XNQ69szB49AhSaT27JE9MYsXy8ybJxw4UHmAYE6O3Na8eeUBgjExnnlecp+FC+Vsr+7dgXXr9B5N7Y0ZIxcpXbpIWWtgoN4jIqI68Ep8BCpbQ1sswNy5wNChnnpBVVdqDBggn1us1DCHCy4A1qyR98ott+g9mto5fBjo1Emuz/Ts4ky68LlkKr/EjvnrMjAzORVFZQ4UlztRmxdoARAaGICwICtG9k7EzT3iERVSxUpTbq4kUFu2yDkZy5d7pkvbunVyATtvnpSIAdI6dMwY6RJjhEMOyTWlpbIRtaAA2LHDXB3wVq+WiQNFkfa13brpPSIiqiWvxUdALohvv11Kn6ZPB+65xx0v4WRVVWqEhEhHvocfNtdnLAFvvy0TxAMHSqmcmQwZIhOmV14p+76YvPsVn0mmSsqdGL94B+aty4DFApTa1Xo/ZohNgaoBQ3vEY1z/jggJ/KfTz4nnZHToIB2C3HlOhtMp5RCTJknHI0AuYm+8sfIAQf6imlPF2UzPPgu89JLeo3FNSYlsFt+1S8p1XnlF7xERUS14NT4CwPffA9dfLxOAnuj4WV2lxoMPStLGSg1zysoCmjWT65uDB4HYWL1H5JqKqpPwcGDrVp5P5od8Ipn6My0HD87dgIISO0od9Q8Spwq2KogMsWHabd2Q1DRMNhb+9BNw1lmS7LjrnIyCAlkenjIFSE+X2yIjKw8QTEhwz/OQfpYtk5KTVq2kPNQMSfFTT8nBwx07Ahs2cM8BkYl4NT4mxMjk4lVXyUr8E0/IZ4e7rF8vk4ys1PBdAwbIlolp06RE1Oiys6V7X1YW8M470tyE/I6pk6kyhxMvLdqOhRv2u2Wm7UyCrQoGH92O52Y8haCGMZJItW1b/wdOS5ME6oMP5AwfAEhMlIYSd90FRETU/znIGJxOScIzM+XAyl699B5RzdaulTp2QMZb8T0RGZrX46NNweD4YDz3xGAE5eXICtF779V/wqimSo3Ro+Uz1AyTUuSaiiYOF14o5eVGN2yYjPnSS4FffvF8J2cyJNMmU0VlDgz7YA12HCzwyGxbdYLtZeh0dC9m398HYUn12DeiaRIYJk2SQKH+8xr69JFZtkGDeICgr3r8cWkTfP/9MvtmVGVlQI8eUrbw2GMyZiIyPF3j4+E9mG3fhLBPP6lfDKuuUuPf/5Z9NazU8E1FRbK3uKhIqjcSE/UeUfW++05aoYeEyP751q31HhHpxJQpdFGZA4Onr8Z2LwcKACi1BWFbs3YY/HshisoctX+A8nJp2ZqUBFxyCfDVVxJw7rhDSqhWrACuu46JlC+rOMRv/nzAbtd3LDV59VVJpNq0kTNAiMjwDBEfL7gHRY46ztOmpcmEYosWwKOPSiKVmAi89Zac0ffGG0ykfFlYmOy3A4DPPtN1KDXKywPuvVe+f/VVJlJ+znQrU2UOJ26Z8Qe2HyxAmZcDxYmCrArObhaJuSMvQJDVhcQnOxuYMUNWIjIz5bbYWGDUKFmhMOshrlR7mibnnmzfLh2LBg7Ue0Sn27xZVqUcDmDlSkn8icjQTBsfa6rUGD1a9ilzgtF/LF4se6c6dJA4acQyzopmUhdeCCQn8/3p50y3MvXSou3YoXOgAIAyh4rtmQV4adGOmn9wxw6ZvYiPB555RhKps88GZs4E9u2Tjm5MpPyLxSJ11oCsUhqN3S579RwOaXzCRIrIFEwXH6ur1Bg+XJpNrFghqxS8UPUv/fpJh+SdO6Vix2iWLJFEKihIvvL96fdMlUz9mZYjm2l1DhQVSh0qFm7IwNr0nJP/QNPkl61/fznEbcYM6WzUv7/cvmWL1H176oBfMr7bbpOv33xT2XTEKCZMADZulPau48frPRoicoFp4iMAHD0qpVGtWlUmTg0bypERe/cCn3zCs+z8mdVaeWjvp5/qO5ZTFRRIh2UAeOEFnmVGAExU5ldS7kSficuRdaxM76GcJi4iCCvHXoYQ5z+zbJMny9I0IAnTHXdIZ76OHXUdJxlM795S2vLJJ3JBYQTbt8uZUuXl0v7/iiv0HhERnYEp4mNggFRqTJ4sB+2WlMgPdOokpXzDhnGCkSqtWSPdY5s0kb1yRln9uf9+4N13pQz+998l8SO/Z5qVqVcX70BBiTE36xcUl2P8f2ZJKd8998gFabNmMvOWkSHtYZlI0akqGlEYpdTP6QRGjJBEauRIJlJEJmHo+Fhix/gZp1RqlJQAV18tlRpbt8rnDRMpOtH550tTh0OH5HxGI1i+XBIpm03K+5hI0T9MkUzll9gxf12GYcoXTlXq1DDPHoP8wlKge3e5OE5LA8aNk9IFoqoMGSIfyj//LAFDb5Mny2xg8+ZS6kdEhmf4+OhQMS+9FPnLkyVhuvdemXBcvBi48kpjNhcg/Z24t9gIpX5FRbI9A5By1HPO0Xc8ZCimSKbmr8sw/OetEqBgwYyv5ZDT228HAgP1HhIZXcOGMlurqsC8efqOJSVFAgQATJ8OREXpOx4icokp4iOABU++yUoNqp2K6o0vv6wsC9XLs88CqalAly7AU0/pOxYyHMMnU6qqYWZyqldOcK+PEsWGGfsB1RQ70MgwKoKFnjNvqiptXktLZe+WEVu1E9FpTBMfbUGYEZQItUGM3kMhM2nbVjo9HjsmB+Tq5bff5JyzgABg1ixOltNpDJ9M/bYnu26H4+qgsMyB1alH9R4Gmck11wAREbKiuXu3PmN45x05J6NxYyn1IyJTYHwkn6f3MSIlJbKXWNOAJ59kl0mqkuGTqWU7s1Bc7tR7GC4psTuxbGeW3sMgMwkJAW66Sb7XY3UqLa2yZOHdd4EYzhwTmQXjI/m8oUNlRWjxYmmp720vvCATnR07As895/3nJ1MwfCuStek5cKVybsRFCRjSPR7tGkcgQLFg8s+7MfmXlFo919gr2+PyDnFo3kC6Cu04WIAJS3Zh3d5cl+6vacDadM68US3dfjvw0UeSTP33v97bkK1p0kWrqAi4+Wbghhu887xE5BbejI/Xdm2Guy9uhY5NIhFoVbBwfQbGLvzL5fszPlKdNG4snWWXLAEWLABGjfLec69dK82YFEXK+4KDvffcZCqGXplSVQ0pWYUu/Wzn5lHIL7HjYH7dNylef24zAMDiLYeQmVeCnq0aYta/khAXEeTyY+w+XAiTHN1FRnHZZUDTpsCePdJNz1vefx/45RcgNhZ4+23vPS8R1Zu342OHJhFwqhr2Hi2q82MwPlKd6HGMSFkZcNddsqd4zBigZ0/vPTeZjqGTqb05xVBcnKV/dP5m3DLzD2zPLKjz842asx79pyTjyS//wo3vrkZRmQMRwTacd1YDlx9DsViw92hxncdAfiggALj1VvneW6V+GRnAY4/J91OnAo0aeed5icgtvB0fX1+yCze+uxrJf2fX+TEYH6lObrgBCA2VRhDp6d55zldfBbZtA9q0AV580TvPSaZl6GQqLbsQVsV7PV+3nhBoLACsAfLch2oxm2dVLEjLrvvMHfmpipm3efMAu4cP39Q0Oevl2DHguuukJp2ITMXb8dEdGB+pTsLDJVYBwGefef75Nm2SZAqQw3lDQz3/nGRqhk6mSu0qNJcqwt0rQLFg4pCuCLIGYNFfmdi8P9/l+2oASh3m2BBMBnLeeUCHDsCRI3KIryfNni2beaOjpemE0Q+pIaLT6BUf64PxkersxFI/T5aK2u3Svc/hAB58EOjd23PPRT7D0MmU3al69HemKsE2BTOH90D/zk3xy87DeHT+5lrdX9M0lBv0JHoysBNPe/dkXfjBg8Ajj8j3kyfLXi0iMh094mN9MT5SnV15pezv3bFDVo48ZcIEYONGICEBGD/ec89DPsXQyZQtQPHqpHlUiA2f3n0B+naIwxcb9uOe2etR7qzdB7/FYkGg1dB/rWRUt90mX7/+Gih0bWN5rWgacP/9QF4e0L8/cMcd7n8OIvIKb8dHd2B8pDqz2SpL0j21t3j7dmmFDkiDpvBwzzwP+RyLZuDWOst2HsYjn2/CMRcOJRzaIx5JCQ1wYetYNI8OwfbMfGw/WICl2w9j6fbDGNytBSYO6YrtmfkYMHVVlY+x8N4L0SMhBnnF5fhq44HjBRQrdx/Byt1HXBu0vQStD/+KpOahaNeuHdq2bYt27dohLi4OFrNFPvK+iy4CVq+W1amKsgZ3mTcPuOUWOSR42zYgPt69j09EXuPt+Hhlp8a4slNjdG0RjbaNI5B+tAjr0nOwNj0X89ZluDRmrbwYcX9/jy6xAWjXrt3xGNm6dWuEhITU6vWTH/r9d6BXL6BZM2DfPmne5C5Op8TfNWvkyJAZM9z32OTzDH3OVKvYcDhU13K9pIQGGNy98uKwU7ModGoWhf25JVi6/fDxGbyaHq9JlJwhEB0aiLsuanX89oISu8vJlKpZ8OuihViWd/Ck2yMjI48nVicGkbZt2yI6OtqlxyY/cPvtVSZTqqphb04x0rILUWpXYXeqsAUoCLYpaBUbjpYxoVBq2ox+5IjUfwPAxIlMpIhMztvxsVPTyJMeI6FhGBIahgGA68kUFGz6dSnWnRIfLRYLzjrrrCpjZEJCAqxWQ1+qkLdccAGQmAikpgIrVgCXXw7ADfERkLL3NWuAFi2k1I+oFgy9MqWqGjr+50eUuaHG+rmBHXH3xYm4/9P1+GHrITeMrmqBCvBC52NISdmN3bt3IyUlBbt27UJ+fvVNLOLi4k4KIhXft2nThrN1/iY7G2jaFKoG/Pb7diw7VI616TlIySqEYrHAqligQYOmyTYrCyxwqBpUTUPbuHAkJcSgb4c4XNQ69uTgceutwOefA337SoMLrpISmZop42OABdP62JCSkoKUlBTs3i1xMi0tDU5n1Y0prFYrWrduXWWi1bx5c1Z8+Jvnn4f60sv47d4nsGzgcPfEx5QUoEsXoLQU+P57YMAA/V4fmZKhkykAGDQ1+aSW5XW1+OHeSMk6hoc/31T/QdXgnOaR+O7Bk7u/aJqG7Ozs48lVRQCpCCglJdW3Xj91tq7i+4SEBNhsNo++FvK+/BI75t/3X8wMb4+iyAYo1pRa9euyAAgNDEBYkBUjeyfi5h7xiFryfeU5HVu3Aq1anfFxiMj4fCE+AoDdbkdaWtpJsbHi+/3791f7eKGhoccrPE6NkQ0bNmSi5WPyS+yY/8N6zFy+G0VBoSgODKl/fAwKAC69FEhOln3EH3/sodGTLzN8MvXCd9vw0ep0UzSAtViAu3q1wvODOrl8H1VVceDAgSoTrdTUVDgcVdfDW61WJCYmVhlEmjdvDkXhJl8zKSl3YvziHZi3LgMWpxOlWv0vAkJsClRVw9Ctv2Dc99MQ8uYE4KGH3DBaIjICX4+PAFBcXIy///77tBi5e/duZGdXf4BwgwYNToqLJ5bWR0RE1PflkBedFB8tcixAfYXYFKgaMDQoF+NeGIGQhtHSgCImpv4DJr9j+GQqOeUIRs1Zj6Jy459NERoYgBnDe+DiNrFueTy73Y709PTTAkhKSgr27dtX7f1CQkLQpk2b00oi2rVrh9jYWI/P1mmaxhnBWvgzLQcPzt2AghI7Sj3QNjjYXopI1Y5pD16BpET3vDeJSH/+HB8BIDc393h8PDVOFtbQEbVp06ZVJlqtW7dGUFCQ28ZXFcbH2vF8fCxDZGkhpp0fiaQ7rnf745N/MHwypaoaLnjtF2QdK9N7KGfUOCIIvz91+Zk3OrpBcXEx9uzZU2WilZWVVe39oqOjq22EERkZWe9xVQSKRYsWISMjAy1btkTv3r05E1iFMocTLy3ajoUb9rtlpu1Mgm0KBndrgecGdUKQ1Y1dkIhIF4yPVdM0DYcPH66ybPDvv/9GeXl5lfdTFAUtW7asMtFq2bIlAurZPY7x0XWMj2Qmhk+mAGBmcire+GmXV36h6irEpuCxfu3x796Jeg8FeXl5p23wrQgoBQXV19c3adKkykSrdevWCA4Odvn53333Xaxfvx4WiwW7d+/Go48+imuvvZazcScoKnNg2AdrsONggUdm26oTbFXQqVkkZo/oibAgdsgiMjvGx9pxOp3IyMioMtFKT0+Hqlb99xgYGFhtI4ymTZu6HN8YH8+M8ZHMxhTJVH6JHee/+rNbuhZ5SpBVwZ9PX4GoEOM2hdA0DVlZWdU2wigrq3p202KxoGXLlqfN1PXr1++0lrW5ubm44IILsHHjRoSGhgKQVbSK70kCxeDpq5F6pEiX93SQVUFiozAsvLcXAwaRyTE+uk9ZWVm1jTAyMzOrvV9YWNhpq1k9e/ZEmzZtTtq/zPh4ZoyPZEamSKYA4PlvtmL+ugyvzlK4Ktiq4OakeLx4bWe9h1Jnqqoen607NdGqqm2tzWZDcXHxacnU4sWL8d///hePPvoocnNzMWDAAJx11lnefCmGVuZw4pYZf2D7wQJdL36CrArObhaJuSMvYEkDkckxPnpeYWHh8UYYp8bJnJyc037+iSeewEsvvYTAwMDjtzE+1ozxkczKNGn3uP4d8eO2Qyg1YG14VKgN467uqPcw6qWiVrxly5bo16/fSX9WXl5+fLauIoCUlJSgtLQU4eHhJ/3smjVrkJubi4KCAiQnJyM1NRWvv/46NE2Dw+FAeno6YmJi0LBhQ2++PMN4adF27NA5UABAmUPF9swCvLRoB16+3twXOUT+jvHR88LDw3Huuefi3HPPPe3Pjh49elojjMsuu+ykRAqoOT5aLBbY7Xbs2bMHiYmJp93XHzA+klmZZmUKANam52D4h2sMVRsebFMwZ0RP9EhgO00AeOihh2C32/Hee+/h8OHDGDt2LAYPHozrrrsOeXl5uPrqq7FmzRrExMRU27b21ATNV/yZloM7Zhnv/Tt7RE8k8f1LZGqMj8ZXU3wEgC1btqBLly5QFAWtWrWqMkbGx8fXuxGGETE+kpmZZmUKAJISYjC4WwssXL/fEOUMwVYFg7vFM1CcoLS0FElJSQBkr1VQUNDxzklhYWEIDg5GeHg4cnJy8Mcff+CPP/447TGaNWtWZRBJTEz0eNtaTykpd+LBuRsMFSgAOa/jgc82YOXYyxAS6HsBmshfMD4aX03xEZAVroSEBOzduxd79uzBnj17sHjx4pMeIygo6PjRJ6c2w4iLizNlIwvGRzI7U61MAVJTe+vMP7AtkzW1RrRp0yZMmDABHTt2xIEDBxAREYEHH3zwpLpwTdNw6NChKs8G2bNnT41taxMSEqpMtM466yxDz9Y9981WLOCeBiLyIMZHY3MlPgKSdKWmpla5P+vQoUPVPn5ERMRpZ0tWfB8dHe3hV1d3jI9kdqZLpgB2ezG6H3/8EWvWrIHT6cSjjz5aqw9xp9OJffv2VZlo7d27t8a2tVXN1rVt2xZNmjTRdbaO3baIyFsYH42tPvERAAoKCqpthJGXl1ft/Ro1alRlotWmTRuEhITU70XVA+Mj+QJTJlOABIzhH67B9kyeQ+AvysrKjs/WnZpoHTx4sNr7hYeHV1kS0bZtWzRo0MDj4+Y5METkTYyP/kfTNGRnZ5/Wjbfia0lJSbX3jY+PrzLRSkhIgM3m2QSC8ZF8gWmTKaDihOwdWLghw4snZMfjuUEdWbpgMMeOHTs+W3dqopWbm1vt/WJjY6tMtNq0aeOWsz9UVcMFr/2CLAN22TpVXEQQ/njqciiK+WruiehkjI9UQVVVHDhwoMpEKzU1FQ6Ho8r7Wa3W440wTo2TzZs3P+kMrbqNi/GRfIOpk6kKa9Nz8MBnG1BQYvfILFywVUFkiA3TbuvGri4mdPTo0SpLIlJSUlBcXFzt/Vq0aFFl2WCrVq1cblubnHIEo+asR1G588w/rLPQwADMGN4DF7eJ1XsoROQmjI9UE7vdjr179540AVkRJ/ft21ft/YKDg4/HxlMnI2NjY10qrWd8JF/hE8kUIN1gxv+4A/PWZkCxACVumIkLsSlQNWBoUjzGXd2R3Vx8jKZpyMzMrDLRSk1Nhd1ur/J+AQEBNbatPXG27oXvtuGj1ekwwy+ZxQLc1asVnh/USe+hEJEbMT5SXZSUlGDPnj1VJlpZWVnV3i8qKqraRhiRkZHHf47xkXyFzyRTFfJL7FiwLgMzklNRWOZAid2J2rxCiwUIsQUgPMiKe3onYkiPeG469EMOh+Ok2boTE619+/ahul+b4ODgkxphrAi+AIfKzvz+ee3Gc9CjZQyaRgWj3KliU0Yexi/egd2HC10es8UCPNK3LYYmxSMmLBB7sgrx+tJdWLHriMuPcU7zSHz3YG+Xf56IzIPxkdwlPz//tJL6iv8vKCio9n6NGzc+nlxtanI1sp1nbn7hjvj4xFXtcW3XZmgUHoRSh4pdh45h0s+78XvqUZcfg/GRquNzyVQFVdXw255sLN91BH+mHUVKViEUiwVWxQINOH7iuAWAQ9WgahraNQ5HUkJD9O0Qh16JDVkbS1UqLS09abbuxIBy+PDhE37SgvjHFkKxnflsrPTxA7FhXy52HTqGi9vEIj4mFAfzS3DpxBUudzm6r09rPHl1B2TkFOPP9BwMOqcpAhQL+k9JRkqWa0EnyKpg54tXm/KsEiJyDeMjeYqmacjKyqq2EUZZWcX+KO/Gx6m3nAdFsSCnqBznxkfjnOZRKCl3otvLP6HE7lqZIeMjVcdnk6lTqaqGfTnFSMsuQqnDiXKHikCrgmBrAFrFhqFlw1D+glC9FRQUHA8c63btw1clHaAqZ+5q1blZJLZmymxei+gQrHqyLwBg4NRkbMusfpavQoBiwdqnr0BMWCAGTU3G1swCPNqvHR7u2xYL12dg7MK/XBp/iC0Aix/ujYTYMJd+nojMj/GRvEFVVWRkZCAlJQV/bEvFrION4bR4Pj6eKirEhs3PXwkA6P36MmTkVt/p8ESMj1Qdv+ldqigWJMSG8ZeAPCoyMhLdu3dH9+7d0XjnYSz9fBOOlVXdKelEW08ICDar7LlyOFWXuxw1jQpGTFggnKp2/LG27M8HAHRqGlnTXU9iVSxIyy7i7wmRH2F8JG9QFAUtW7ZEy5YtobQ4jHleio8Vru3aDN1bNkC3s+RIlEV/ZbqcSAGMj1Q9v0mmiLyt1K5Cq+XW2tDAAEy4qQsA4P1VaTjiYrBoFC6lEieWKxSXS5BqFHHmMooKGoBSh/E7KxERkXl5Mz5WuKRtLAZ3jwcA5BWXIzklu1b3Z3yk6tTvkAAiqpbdqdZqc3dMWCDmjrwAPRJi8Nmf+/Dajztdvu+RQgkqIbYAVFTjVByaWZuAo2kayg18Ej0REZmfN+NjhbEL/0KbZ37AkOmroSgW/O+mLujesoHL92d8pOowmSLyEFuAAle3GTSPDsGCey9E1xbRmLb8bzz91ZZaPdfB/FLkFpcjQLHgnOZRAIAuLaIBADsOHXP5cSwWCwKt/FggIiLP8WZ8tCoWBAb8Ux6oalibnousAplkTKxFyR7jI1WHZX5EHhJsUyD9sM7si1G90CQqGPtzixESGHD8LItvNh3A5v35GNytBSYO6YrtmfkYMHXVafd3qhpmJqfiias64J3bumFNmnTzczhVTP91j8tjtgAItvK8GCIi8hxvxscmkcFY9NDFWL3nKI4WlaNzs0i0iQtHSbkTa9JyXB4z4yNVh8kUkYe0ig2HQ3WtjqFJVDAAoEWDUIy4qNXx27dnFmDz/vzjM3g1Pd57K/cg2BaAm7vH45ouzbDnSCEmLN1Vq7M4HKqGVtxcS0REHuTN+HiszIHN+/OQlBCDqBAb8kvKsWxnFqat+Bv7copdHjPjI1WHyRSRh7SMCYXqYlF4wrjva/zzDk0iAEjCVB1VA978aTfe/Gm364M87TE0tGwYWuf7ExERnYk342N+iR13zlpbuwFWgfGRqsPiTyIPURQL2saFu+WxerWOxbebD+CHrYfc8njVadc4nOfJEBGRRzE+ki/hyhSRByUlxGBbZkEtG8Cerv+UZLeMpyYWC5CU0NDjz0NERMT4SL6CK1NEHtS3QxxCA82xYTXEFoC+HeL0HgYREfkBxkfyFUymiDzootaxx897MrqIICt6JXLmjYiIPI/xkXwFkykiD1IUC0b2TkSwzdi/aiE2BSN7J0JRWA9ORESex/hIvsLY72AiH3Bzj/hanfSuB1UDhvSI13sYRETkRxgfyRcwmSLysKgQG4b2iEewQU9OD7YqGJoUj6gQm95DISIiP8L4SL7AmO9eIh8zrn9HRBr0wzgq1IZxV3fUexhEROSHGB/J7JhMEXlBSGAApt3WzXC14cE2BdNu7YYQk3RUIiIi38L4SGZnrHcukQ9LSojB4G4tDFPOEGxVMLhbPHokxOg9FCIi8mOMj2RmxnjXEvmJ5wZ1QqdmkQjSOWAEWRV0ahaJ5waxfIGIiPTH+EhmxWSKyIuCrAGYPaInEhuF6RYwgqwKEhuFYfaIngiysnyBiIj0x/hIZsVkisjLwoKsWHhvL5zdLNLrJQ3BVgVnN4vEwnt7meawRCIi8g+Mj2RGFk0zeod/It9U5nDipUU7sHBDBkrtqsefL9gmNeDPDerIGTciIjIsxkcyEyZTRDpbm56DBz7bgIISO0od7g8awVYFkSE2TLutG5K4mZaIiEyC8ZHMgMkUkQGUlDsx/scdmLc2A4oFKHHDTFyITYGqAUOT4jHu6o5s70pERKbD+EhGx2SKyEDyS+xYsC4DM5JTUVjmQIndidr8hlosQIgtAOFBVtzTOxFDevDkdiIiMj/GRzIqJlNEBqSqGn7bk43lu47gz7SjSMkqhGKxwKpYoAHQNA0WiwUWAA5Vg6ppaNc4HEkJDdG3Qxx6JTaEolj0fhlERERuxfhIRsNkisgEVFXDvpxipGUXodThRLlDRaBVQbA1AK1iw9CyYSgsFgYHIiLyL4yPpDcmU0RERERERHXAc6aIiIiIiIjqgMkUERERERFRHTCZIiIiIiIiqgMmU0RERERERHXAZIqIiIiIiKgOmEwRERERERHVAZMpIiIiIiKiOmAyRUREREREVAdMpoiIiIiIiOqAyRQREREREVEdMJkiIiIiIiKqAyZTREREREREdcBkioiIiIiIqA7+DwSFdTrupboZAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 1080x288 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "label_dict = {i: str(i) + \", \" + str(t) for i, t in solution.items()}\n",
    "edge_color = [\"red\" if solution[u] == (solution[v] + 1) % n\n",
    "              or solution[v] == (solution[u] + 1) % n else \"black\"\n",
    "              for (u, v) in G.edges]\n",
    "label_dict_bf = {i: str(i) + \", \" + str(t) for i, t in solution_brute_force.items()}\n",
    "edge_color_bf = [\"red\" if solution_brute_force[u] == (solution_brute_force[v] + 1) % n\n",
    "                 or solution_brute_force[v] == (solution_brute_force[u] + 1) % n else \"black\"\n",
    "                 for (u, v) in G.edges]\n",
    "\n",
    "# Draw the walk corresponding to the dictionary presented above on the graph\n",
    "fig, ax = plt.subplots(1, 2, figsize=(15, 4))\n",
    "for i, a in enumerate(ax):\n",
    "    a.axis('off')\n",
    "    a.margins(0.20)\n",
    "nx.draw(G, pos=pos, labels=label_dict, edge_color=edge_color, ax=ax[0], **options)\n",
    "nx.drawing.nx_pylab.draw_networkx_edge_labels(G, pos=pos, ax=ax[0], edge_labels=nx.get_edge_attributes(G, 'weight'))\n",
    "nx.draw(G, pos=pos, labels=label_dict_bf, edge_color=edge_color_bf, ax=ax[1], **options)\n",
    "nx.drawing.nx_pylab.draw_networkx_edge_labels(G, pos=pos, ax=ax[1], edge_labels=nx.get_edge_attributes(G, 'weight'))\n",
    "plt.axis(\"off\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The left graph given above shows a solution found by the parameterized quantum circuit, while the right graph given above shows a solution found by the brute-force algorithm. It can be seen that even if the order of the vertices are different, the routes are essentially the same, which verifies the correctness of using parameterized quantum circuit to solve the TSP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Applications\n",
    "\n",
    "The TSP naturally applies in many transportation and logistics applications, for example, the problem of arranging school bus routes. The school bus application provides the motivation for Merrill Flood, a pioneer in the field of management science, to study TSP research in the 1940s. More recent applications involve food delivery route management [1] and power delivery for cable firms [2]. \n",
    "\n",
    "Other than those transportation applications, TSP also has wide usefulness in other management problems like scheduling of a machine to drill holes in a circuit board [3], reconstructing an unknown fragment of DNA [4] and scheduling optimal route in construction management [5]. Some consulting companies like [Nexus](https://nexustech.com.ph/company/newsletter/article/Finding-the-shortest-path-Optimizing-food-trips) have utilized this to provide management service.\n",
    "\n",
    "The TSP, as one of the most famous optimization problems, also provides a platform for the study of general methods in solving combinatorial problem. This is usually the first several problems that researchers give a try for experiments of new algorithms.\n",
    "\n",
    "More applications, formulations and solution approaches can be found in [6]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_______\n",
    "\n",
    "## References\n",
    "\n",
    "[1] Bräysy, Olli, et al. \"An optimization approach for communal home meal delivery service: A case study.\" [Journal of Computational and Applied Mathematics 232.1 (2009): 46-53.](https://www.sciencedirect.com/science/article/pii/S0377042708005438)\n",
    "\n",
    "[2] Sloane, Thomas H., Frank Mann, and H. Kaveh. \"Powering the last mile: an alternative to powering FITL.\" [Proceedings of Power and Energy Systems in Converging Markets. IEEE, 1997.](https://ieeexplore.ieee.org/document/646046)\n",
    "\n",
    "[3] Onwubolu, Godfrey C. \"Optimizing CNC drilling machine operations: traveling salesman problem-differential evolution approach.\" [New optimization techniques in engineering. Springer, Berlin, Heidelberg, 2004. 537-565.](https://link.springer.com/chapter/10.1007/978-3-540-39930-8_22)\n",
    "\n",
    "[4] Caserta, Marco, and Stefan Voß. \"A hybrid algorithm for the DNA sequencing problem.\" [Discrete Applied Mathematics 163 (2014): 87-99.](https://www.sciencedirect.com/science/article/pii/S0166218X12003253)\n",
    "\n",
    "[5] Klanšek, Uroš. \"Using the TSP solution for optimal route scheduling in construction management.\" [Organization, technology & management in construction: an international journal 3.1 (2011): 243-249.](https://www.semanticscholar.org/paper/Using-the-TSP-Solution-for-Optimal-Route-Scheduling-Klansek/3d809f185c03a8e776ac07473c76e9d77654c389)\n",
    "\n",
    "[6] Matai, Rajesh, Surya Prakash Singh, and Murari Lal Mittal. \"Traveling salesman problem: an overview of applications, formulations, and solution approaches.\" [Traveling salesman problem, theory and applications 1 (2010).](https://www.sciencedirect.com/topics/computer-science/traveling-salesman-problem)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
